Induction for series and sequencesAQA A-Level Further Maths: Revision notes

Mathematical induction proves a statement $P(n)$ for all positive integers $n$. It works like a line of dominoes: if the first one falls, and each one knocks over the next, they all fall.

• Basis step: show $P(1)$ is true.
• Inductive hypothesis: assume $P(k)$ is true for some positive integer $k$.
• Inductive step: using that assumption, show $P(k+1)$ is true.
• Conclusion: state that $P(1)$ is true and $P(k)\Rightarrow P(k+1)$, so $P(n)$ is true for all positive integers $n$ by induction.

To prove $\sum_{r=1}^{n}f(r)=F(n)$, check both sides when $n=1$, then assume $\sum_{r=1}^{k}f(r)=F(k)$. The sum to $k+1$ terms is the sum to $k$ terms plus the $(k+1)$th term: $\sum_{r=1}^{k+1}f(r)=\sum_{r=1}^{k}f(r)+f(k+1)=F(k)+f(k+1).$ Then show algebraically that $F(k)+f(k+1)=F(k+1)$. This target $F(k+1)$ is the formula with every $n$ replaced by $k+1$.

Prove that $\sum_{r=1}^{n}(2r-1)=n^2$. Basis: $n=1$: LHS $=1$, RHS $=1^2=1$, so true for $n=1$. Hypothesis: assume $\sum_{r=1}^{k}(2r-1)=k^2$. Step: $\sum_{r=1}^{k+1}(2r-1)=k^2+\big(2(k+1)-1\big)=k^2+2k+1=(k+1)^2$, which is the formula with $n=k+1$. Conclusion: true for $n=1$, and true for $n=k$ implies true for $n=k+1$, so true for all positive integers $n$ by induction.

Sums of $r^2$, $r^3$ or $\frac{1}{r(r+1)}$ need more care, but the method is identical. For $\sum_{r=1}^{n}r^2=\frac16n(n+1)(2n+1)$: $\frac16k(k+1)(2k+1)+(k+1)^2=\frac{k+1}{6}\left[k(2k+1)+6(k+1)\right]=\frac{(k+1)(k+2)(2k+3)}{6}.$ For $\sum_{r=1}^{n}\frac{1}{r(r+1)}=\frac{n}{n+1}$: $\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}=\frac{k(k+2)+1}{(k+1)(k+2)}=\frac{(k+1)^2}{(k+1)(k+2)}=\frac{k+1}{k+2}.$ Standard results you may need to prove: $\sum r=\frac{n(n+1)}{2}$ and $\sum r^3=\frac14n^2(n+1)^2$.

For a sequence with $u_{n+1}=f(u_n)$, prove a closed formula by substituting the hypothesis for $u_k$ into the recurrence to get $u_{k+1}$. Example: $u_1=3$, $u_{n+1}=3u_n-2$. Claim $u_n=2\times3^{n-1}+1$. Basis: $2\times3^{0}+1=3=u_1$. Step: $u_{k+1}=3\left(2\times3^{k-1}+1\right)-2=2\times3^{k}+1$, which is the formula with $n=k+1$.

Marks are lost for a missing or vague conclusion. Write: ‘The result is true for $n=1$. If it is true for $n=k$, then it is true for $n=k+1$. Therefore, by mathematical induction, it is true for all positive integers $n$.’ Show the basis step with both sides evaluated, and state the inductive hypothesis explicitly.