Finite Sums and Induction: Prove the Next Case

Worked example

An arithmetic progression adds the same real number $d$, the common difference, at each step. If its first term is $a$, then $a_j=a+(j-1)d$: reaching position $j$ takes $j-1$ steps. For $a=6$ and $d=3$, the terms begin $6,9,12,15$. Thus $a_4=15$, whereas $S_4=6+9+12+15=42$.

To derive a sum formula, write the same $n$ terms once forwards and once backwards. Add the two rows position by position. Each position totals $a+a_n$, and there are $n$ positions: $$2S_n=n(a+a_n).$$ This doubles the original sum even when $n$ is odd; the middle term then occurs once in each row.

Substitute $a_n=a+(n-1)d$ and divide by 2: $$S_n=\frac{n}{2}\bigl(2a+(n-1)d\bigr).$$ The four-term example gives $S_4=\frac42(12+9)=42$. The formula gives a sum; it does not replace the separate formula for $a_n$.

For any sequence, not just an arithmetic one, appending the next term gives $$S_{k+1}=S_k+a_{k+1}.$$ This identity comes from the definition of a partial sum. It will be the starting point for the induction step.

Worked example

A geometric progression multiplies by a fixed ratio at each step. Consider $G_n=\sum_{j=1}^{n}3\cdot2^{j-1}$, with terms $3,6,12,\ldots$. We will prove $P(n):G_n=3(2^n-1)$ for every integer $n\ge1$. Here $n$ counts terms; the exponent of the last term is $n-1$.

Base case: $G_1=3$, and $3(2^1-1)=3$, so $P(1)$ holds. For the induction step, choose an arbitrary integer $k\ge1$ and assume $G_k=3(2^k-1)$. The target is $G_{k+1}=3(2^{k+1}-1)$; writing this as a target does not make it an established equality.

Begin with the actual sum. Its new term is $3\cdot2^k$. Only the second line below uses the induction hypothesis: $$\begin{aligned}G_{k+1}&=G_k+3\cdot2^k\\&=3(2^k-1)+3\cdot2^k\\&=3(2\cdot2^k-1)\\&=3(2^{k+1}-1).\end{aligned}$$ The last equality uses $2\cdot2^k=2^{k+1}$.

We have established the target from the assumption, for an arbitrary allowed $k$. Starting with the verified case 1, that same implication gives case 2, then case 3, and every subsequent integer case. This is why the proof reaches beyond a few numerical checks.

Worked example

Why can’t the step replace the base case? Return to $G_n=\sum_{j=1}^{n}3\cdot2^{j-1}$. Someone proposes the wrong formula $H_n=3\cdot2^n$. It has the correct increment: $$H_{k+1}-H_k=3\cdot2^k.$$ But $H_1=6$, whereas $G_1=3$.

The proposed values stay 3 above the actual sums: $H_n-G_n=3$. Matching successive differences determines a sequence only after its starting value is fixed. Checking the base case catches this constant error immediately.

For a new induction proof, write three lines before the algebra: the first allowed index, the exact hypothesis at $k$, and the target at $k+1$. Then derive the change in the actual sum from its bounds. These choices matter more than memorizing a stock proof.