Induction for series and sequences

Induction for series and sequences

Spec A1 · AQA A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Induction proves a statement P(n)P(n) for all positive integers nn in four stages: basis, hypothesis, step, conclusion.
  • In the step you assume P(k)P(k) only and must deduce P(k+1)P(k+1).
  • For a sum: the sum to k+1k+1 terms is the sum to kk terms plus the (k+1)(k+1)th term.
  • Write the target F(k+1)F(k+1) first: the formula with every nn replaced by k+1k+1.
  • For a recurrence uk+1=f(uk)u_{k+1}=f(u_k), substitute the hypothesis for uku_k.
  • Always finish with the full conclusion: true for n=1n=1, and P(k)⇒P(k+1)P(k)\Rightarrow P(k+1), so true for all positive integers nn.

How induction works

If the first case is true and each case forces the next, then every case is true, like a line of dominoes.

Mathematical induction proves a statement P(n)P(n) for all positive integers nn.

It works like a line of dominoes: if the first one falls, and each one knocks over the next, they all fall.

Each of the four stages in the diagram must be written down.

  1. 1

    Basis step

    show P(1)P(1) is true

  2. 2

    Inductive hypothesis

    assume P(k)P(k) is true for some positive integer kk

  3. 3

    Inductive step

    using that assumption, show P(k+1)P(k+1) is true

  4. 4

    Conclusion

    P(1)P(1) true and P(k)⇒P(k+1)P(k)\Rightarrow P(k+1), so P(n)P(n) is true for all positive integers nn

The four stages of an induction proof

In the inductive step, what are you allowed to assume?

Proving a sum formula

Add the (k+1)(k+1)th term to the assumed sum to kk terms, then show the result equals the formula with n=k+1n=k+1.

To prove ∑r=1nf(r)=F(n)\sum_{r=1}^{n}f(r)=F(n), check both sides when n=1n=1, then assume ∑r=1kf(r)=F(k)\sum_{r=1}^{k}f(r)=F(k).

The sum to k+1k+1 terms is the sum to kk terms plus the (k+1)(k+1)th term:

∑r=1k+1f(r)=F(k)+f(k+1).\sum_{r=1}^{k+1}f(r)=F(k)+f(k+1).

Show algebraically that this equals the target F(k+1)F(k+1).

  • Sum to k+1k+1 termssum to kk terms + f(k+1)+\ f(k+1)
  • Target F(k+1)F(k+1)replace every nn by k+1k+1

Worked example

Prove that ∑r=1n(2r−1)=n2\sum_{r=1}^{n}(2r-1)=n^2.

What is the target F(k+1)F(k+1) when F(n)=n(n+1)2F(n)=\frac{n(n+1)}{2}?

Harder algebra in the step

The method is identical; take out the common factor (k+1)(k+1) first and the remaining bracket should factorise into the target.

For ∑r2=16n(n+1)(2n+1)\sum r^2=\frac16n(n+1)(2n+1):

16k(k+1)(2k+1)+(k+1)2=(k+1)(k+2)(2k+3)6.\frac16k(k+1)(2k+1)+(k+1)^2=\frac{(k+1)(k+2)(2k+3)}{6}.

For ∑1r(r+1)=nn+1\sum\frac{1}{r(r+1)}=\frac{n}{n+1}:

kk+1+1(k+1)(k+2)=(k+1)2(k+1)(k+2)=k+1k+2.\frac{k}{k+1}+\frac{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: ∑r=n(n+1)2\sum r=\frac{n(n+1)}{2} and ∑r3=14n2(n+1)2\sum r^3=\frac14n^2(n+1)^2.

∑r2\sum r^2

  • Add (k+1)2(k+1)^2
  • Take out k+16\frac{k+1}{6}
  • Bracket: k(2k+1)+6(k+1)=(k+2)(2k+3)k(2k+1)+6(k+1)=(k+2)(2k+3)

∑1r(r+1)\sum\frac{1}{r(r+1)}

  • Add 1(k+1)(k+2)\frac{1}{(k+1)(k+2)}
  • Common denominator (k+1)(k+2)(k+1)(k+2)
  • Numerator: k(k+2)+1=(k+1)2k(k+2)+1=(k+1)^2

In the r2r^2 proof, what is the bracket k(2k+1)+6(k+1)k(2k+1)+6(k+1) after expanding?

Sequences defined by recurrence

Substitute the hypothesis for uku_k into the recurrence to get uk+1u_{k+1}, and show it matches the formula with n=k+1n=k+1.

For a sequence with uk+1=f(uk)u_{k+1}=f(u_k), the hypothesis gives uku_k as a formula. Put it into the recurrence relation and simplify.

Before proving, check the first few terms by hand to confirm the formula is right: here u2=7u_2=7 and u3=19u_3=19.

  1. 1

    Basis

    check u1u_1 against the formula

  2. 2

    Hypothesis

    assume uku_k equals the formula

  3. 3

    Step

    put it into uk+1=f(uk)u_{k+1}=f(u_k) and simplify

  4. 4

    Conclusion

    state it for all positive integers nn

Induction on a recurrence

Worked example

u1=3u_1=3 and un+1=3un−2u_{n+1}=3u_n-2. Prove that un=2×3n−1+1u_n=2\times3^{n-1}+1.

If uk=2×3k−1+1u_k=2\times3^{k-1}+1, what is 3uk−23u_k-2?

Writing the conclusion

The conclusion must link the basis step and the inductive step; a vague one loses marks.

Write:

‘The result is true for n=1n=1. If it is true for n=kn=k, then it is true for n=k+1n=k+1. Therefore, by mathematical induction, it is true for all positive integers nn.’

Show the basis step with both sides evaluated, and state the inductive hypothesis explicitly.

  • P(1)P(1) true and P(k)⇒P(k+1)P(k)\Rightarrow P(k+1)P(n)P(n) true for all positive integers nn

Which part of a conclusion is essential for full marks?

Try an exam question

Prove by induction that ∑r=1nr2=16n(n+1)(2n+1)\sum_{r=1}^{n}r^2=\frac16n(n+1)(2n+1) for all positive integers nn.

[5 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Find the value of S4S_4.

1 mark, marked against the mark scheme

Revision notes