Further Mathematics · Pearson Edexcel 9FM0 · Topic 1

Proof

Proof by induction: show a statement is true for n = 1, assume it for n = k, then prove it for n = k + 1. Used for sums of series, divisibility and powers of matrices.

  • 1 sub-topic
  • Taught in Year 12
  • 24 practice questions
  • 1 animated lesson
Practice questions (24) Lessons Worksheets All Edexcel Further Mathematics topics

What the specification says

Every sub-topic Pearson Edexcel can examine in this topic, with its reference number from the official specification. The Y12 and Y13 tags show when each sub-topic is usually taught.

  1. 1.1Proof by mathematical inductionY12

Try 3 questions

Easy, medium and hard questions from this topic, each with a worked solutions and the mark for every step. All 24 questions in this topic, free, no account needed.

Proof

Easy

Sum of odd numbers · Year 12 · 4 marks

  1. Prove by induction that, for all positive integers nn, ∑r=1n(2r−1)=n2.\sum_{r=1}^{n} (2r - 1) = n^2.
    (4)
Show worked solutionHide worked solution
  1. Start by checking the first case works.n=1n = 1: left side =1= 1, right side =12=1= 1^2 = 1
  2. Suppose the statement is true when n=kn = k.Assume ∑r=1k(2r−1)=k2\sum_{r=1}^{k} (2r - 1) = k^2
  3. Adding one more term means adding the term with r=k+1r = k + 1.∑r=1k+1(2r−1)\sum_{r=1}^{k+1} (2r - 1)=k2+2(k+1)−1{}= k^2 + 2(k + 1) - 1=k2+2k+1{}= k^2 + 2k + 1
  4. This is the formula with n=k+1n = k + 1, which is what we wanted.=(k+1)2= (k + 1)^2
  5. It is true for n=1n = 1, and if it is true for one value it is true for the next, so it is true for every nn.So the statement is true for all positive integers nn.

Total4

  • M
  • A
  • B
How did it go?

Report a problem with this question

Proof

Medium

Induction with a sum · Year 12 · 5 marks

  1. Prove by induction that, for all positive integers nn, ∑r=1nr(r+1)=13n(n+1)(n+2).\sum_{r=1}^{n} r(r + 1) = \tfrac{1}{3}n(n + 1)(n + 2).
    (5)
Show worked solutionHide worked solution
  1. Basis: check the statement is true for the first value.n=1n = 1: left side =1×2=2= 1 \times 2 = 2, right side =13(1)(2)(3)=2= \tfrac{1}{3}(1)(2)(3) = 2
  2. Assumption: suppose it is true for some n=kn = k.Assume ∑r=1kr(r+1)\sum_{r=1}^{k} r(r+1)=13k(k+1)(k+2){}= \tfrac{1}{3}k(k+1)(k+2)
  3. The sum to k+1k + 1 is the sum to kk plus the next term, where r=k+1r = k + 1.∑r=1k+1r(r+1)\sum_{r=1}^{k+1} r(r+1)=13k(k+1)(k+2){}= \tfrac{1}{3}k(k+1)(k+2)+(k+1)(k+2){}+ (k+1)(k+2)
  4. Take out the common factor 13(k+1)(k+2)\tfrac{1}{3}(k+1)(k+2) instead of expanding.=13(k+1)(k+2)(k+3)= \tfrac{1}{3}(k+1)(k+2)(k + 3)
  5. Show it is the original formula with nn replaced by k+1k + 1.This is 13n(n+1)(n+2)\tfrac{1}{3}n(n+1)(n+2) with n=k+1n = k + 1.
  6. Conclusion: true for n=1n = 1, and true for kk means true for k+1k + 1.So it is true for all positive integers nn.

Total5

  • M
  • A
  • B
How did it go?

Report a problem with this question

Proof

Hard

Induction with divisibility · Year 12 · 6 marks

  1. Prove by induction that 4n+6n−14^n + 6n - 1 is divisible by 9 for all positive integers nn.
    (6)
Show worked solutionHide worked solution
  1. Basis: 9 is divisible by 9.f(1)=4+6−1=9\mathrm{f}(1) = 4 + 6 - 1 = 9
  2. Assumption step.Assume f(k)=4k+6k−1\mathrm{f}(k) = 4^k + 6k - 1 is divisible by 9.
  3. Subtracting 4f(k)4\mathrm{f}(k) cancels the 4k+14^{k+1} terms.f(k+1)\mathrm{f}(k+1)−4f(k){}- 4\mathrm{f}(k)=4k+1{}= 4^{k+1}+6k{}+ 6k+5{}+ 5−4k+1{}- 4^{k+1}−24k{}- 24k+4{}+ 4
  4. What is left is a multiple of 9.=9−18k=9(1−2k)= 9 - 18k = 9(1 - 2k)
  5. Rearrange to write f(k+1)\mathrm{f}(k+1) in terms of f(k)\mathrm{f}(k).f(k+1)\mathrm{f}(k+1)=4f(k)+9(1−2k){}= 4\mathrm{f}(k) + 9(1 - 2k)
  6. f(k)\mathrm{f}(k) is a multiple of 9 by the assumption.Both terms are multiples of 9, so f(k+1)\mathrm{f}(k+1) is too.
  7. Conclusion: true for n=1n = 1, and true for kk means true for k+1k + 1.So it is true for all positive integers nn.

Total6

  • M
  • A
  • B
How did it go?

Report a problem with this question