Lesson 7 · Further induction I: series and divisibility

Learning intentionTo extend Extension 1 induction to harder series and divisibility results, including proofs that start later or step by 2.

Success criteria · I can…

define $P(n)$ and set out an induction proof with clear signposts and conclusions
prove series results written in $\sum$ notation
prove harder divisibility results by rewriting using the assumption
adapt the proof when $n$ does not start at 1 or goes up in steps of 2

ResourcesLesson slides
Practice worksheet
Worked solutions
Induction Coach applet

Lesson flow

LaunchWarm-up · Algebra for inductionSlide 2 Key ideasThe induction template · Using P(n)Slide 3 ExamplesExample 1 · Extension 1 recapSlide 4 ExamplesExample 2 · A series with fractionsSlide 5 ExamplesExample 3 · DivisibilitySlide 6 ExamplesExample 4 · Stepping by 2Slide 7 ExamplesExample 5 · Two different powersSlide 8 Exam-styleExam-style · Induction, then an applicationSlide 9 ThinkSpot the flaw · InductionSlide 10 Exit ticketExit ticketSlide 11

Warm-up · Algebra for induction

Slide 2

(a) Write out the first three terms and the

(k+1)

th term of

\displaystyle\sum_{r=1}^{n}r(r+1)

Show answerHide answer

Answer

1\times2+2\times3+3\times4+\dots

; the

(k+1)

th term is

(k+1)(k+2)

Why

Replace

r

1,2,3

, and by

k+1

for the general next term.

(b) Simplify

\dfrac{k(k+1)(k+2)}3+(k+1)(k+2)

Show answerHide answer

Answer

\dfrac{(k+1)(k+2)(k+3)}3

Why

Take out the common factor

(k+1)(k+2)

rather than expanding:

(k+1)(k+2)\left[\frac k3+1\right]=(k+1)(k+2)\cdot\frac{k+3}3

(c) Given

3^k-1=2M

, write

3^{k+1}-1

in terms of

M

Show answerHide answer

Answer

3^{k+1}-1=2(3M+1)

Why

3^k=2M+1

, so

3^{k+1}-1=3(2M+1)-1=6M+2=2(3M+1)

(d) If

k

is odd, what is the next odd integer?

Show answerHide answer

Answer

k+2

Why

Odd integers go up in steps of 2. This matters in Example 4.

The induction template · Using P(n)

Slide 3

Key idea

Signposts markers look for

Let $P(n)$ be the statement: … (write it out).

Step 1. Show $P(1)$ is true (or the first value). Evaluate each side separately. $\therefore P(1)$ is true.
Step 2. Assume $P(k)$ is true for some integer $k\ge1$ . Write the assumption out in full.
Step 3. Prove $P(k+1)$ is true. Write what you need to show, and say where you use the assumption (“by the assumption”). $\therefore P(k+1)$ is true whenever $P(k)$ is true.
Step 4. Conclude: “Hence, by mathematical induction, $P(n)$ is true for all integers $n\ge1$ .”

Divisibility: write the assumption as expression $=dM$ for some $M\in\mathbb{Z}$ , then substitute.

$S(n)$ can be used instead of $P(n)$ , for example when $P(x)$ is already a polynomial in the question, or always, if you prefer. Be consistent within a proof. Name the statement first, so every step can refer to $P(1)$ , $P(k)$ and $P(k+1)$ . The Induction Coach applet on this page lets you practise setting out these steps in order.

Example 1 · Extension 1 recap

Slide 4

Prove by mathematical induction that for all integers

n\ge1

\sum_{r=1}^{n}r(r+1)=\frac{n(n+1)(n+2)}3.

Show answerHide answer

Answer

Let

P(n)

be the statement

\displaystyle\sum_{r=1}^{n}r(r+1)=\frac{n(n+1)(n+2)}3

.
Step 1.

P(1)

: LHS

=1\times2=2

, RHS

=\dfrac{1\times2\times3}3=2

\therefore P(1)

is true.
Step 2. Assume

P(k)

\displaystyle\sum_{r=1}^kr(r+1)=\frac{k(k+1)(k+2)}3

for some integer

k\ge1

.
Step 3. Need to show

P(k+1)

\displaystyle\sum_{r=1}^{k+1}r(r+1)=\frac{(k+1)(k+2)(k+3)}3

.
LHS

=\dfrac{k(k+1)(k+2)}3+(k+1)(k+2)

(by the assumption)

=\dfrac{(k+1)(k+2)(k+3)}3=

RHS (Warm-up (b)).

\therefore P(k+1)

is true whenever

P(k)

is true.
Step 4. Hence, by mathematical induction,

P(n)

is true for all integers

n\ge1

Why

Mark the use of the assumption, and factorise the common factor instead of expanding. Writing what you need to show first tells you the target for the algebra.

Example 2 · A series with fractions

Slide 5

Prove by induction that for all integers

n\ge1

\frac1{1\times3}+\frac1{3\times5}+\dots+\frac1{(2n-1)(2n+1)}=\frac n{2n+1}.

Show answerHide answer

Answer

Step 1.

n=1

: LHS

=\dfrac1{1\times3}=\dfrac13

, RHS

=\dfrac13

\therefore P(1)

is true.
Step 2. Assume

S_k=\dfrac k{2k+1}

for some integer

k\ge1

.
Step 3. Need to show

S_{k+1}=\dfrac{k+1}{2k+3}

. The

(k+1)

th term is

\dfrac1{(2k+1)(2k+3)}

, so by the assumption

S_{k+1}=\frac k{2k+1}+\frac1{(2k+1)(2k+3)}=\frac{2k^2+3k+1}{(2k+1)(2k+3)}=\frac{(2k+1)(k+1)}{(2k+1)(2k+3)}=\frac{k+1}{2k+3}.

\therefore P(k+1)

is true whenever

P(k)

is true.
Step 4. Hence, by mathematical induction, the statement is true for all integers

n\ge1

Why

The

(k+1)

th term is found by putting

n=k+1

\frac1{(2n-1)(2n+1)}

, giving

\frac1{(2k+1)(2k+3)}

. Combining over the common denominator gives

k(2k+3)+1=2k^2+3k+1

, which factorises as

(2k+1)(k+1)

. The common factor

(2k+1)

cancelling confirms the algebra is on track.

Example 3 · Divisibility

Slide 6

Prove by induction that

5^{2n}+3n-1

is divisible by 9 for all integers

n\ge1

Show answerHide answer

Answer

Step 1.

P(1)

25+3-1=27=9\times3

\therefore P(1)

is true.
Step 2. Assume

5^{2k}+3k-1=9M

for some integer

M

, so

5^{2k}=9M-3k+1

.
Step 3. Need to show

5^{2(k+1)}+3(k+1)-1

is divisible by 9.

5^{2k+2}+3k+2=25\cdot5^{2k}+3k+2=25(9M-3k+1)+3k+2=225M-72k+27=9(25M-8k+3),

which is divisible by 9 since

25M-8k+3

is an integer.

\therefore P(k+1)

is true whenever

P(k)

is true.
Step 4. Hence, by mathematical induction,

5^{2n}+3n-1

is divisible by 9 for all integers

n\ge1

Why

Rewrite

5^{2k+2}=25\cdot5^{2k}

and substitute

5^{2k}

from the assumption. Every term must then contain a factor of 9. Note that

3(k+1)-1=3k+2

Example 4 · Stepping by 2

Slide 7

Think first: what is the first case? What is “the next case” after $n=k$ ?

Prove by induction that

3^n+7^n

is divisible by 10 for all odd positive integers

n

Show answerHide answer

Answer

Step 1.

n=1

(the first odd positive integer):

3+7=10

\therefore P(1)

is true.
Step 2. Assume

3^k+7^k=10M

for some odd

k

and some integer

M

.
Step 3. The next odd integer is

k+2

. Need to show

3^{k+2}+7^{k+2}

is divisible by 10.

3^{k+2}+7^{k+2}=9\cdot3^k+49\cdot7^k=9(3^k+7^k)+40\cdot7^k=90M+40\cdot7^k=10\left(9M+4\cdot7^k\right),

which is divisible by 10.

\therefore P(k+2)

is true whenever

P(k)

is true.
Step 4. Hence, by mathematical induction,

3^n+7^n

is divisible by 10 for all odd positive integers

n

Why

The common error is to prove the case

n=k+1

, but

k+1

is even. Write

49\cdot7^k=9\cdot7^k+40\cdot7^k

so that

9(3^k+7^k)

appears and the remainder

40\cdot7^k

is clearly a multiple of 10. The conclusion must say “for all odd positive integers

n

”.

Watch out

If the statement starts at

n=5

, check

n=5

in Step 1 and conclude “for all integers

n\ge5

”. If it steps by 2, the next case is

k+2

Example 5 · Two different powers

Slide 8

Prove by induction that

7^n-3^n

is divisible by 4 for all integers

n\ge1

Show answerHide answer

Answer

Step 1.

P(1)

7-3=4

\therefore P(1)

is true.
Step 2. Assume

7^k-3^k=4M

for some integer

M

, so

7^k=4M+3^k

.
Step 3. Need to show

7^{k+1}-3^{k+1}

is divisible by 4.

7^{k+1}-3^{k+1}=7(4M+3^k)-3\cdot3^k=28M+4\cdot3^k=4\left(7M+3^k\right),

which is divisible by 4.

\therefore P(k+1)

is true whenever

P(k)

is true.
Step 4. Hence, by mathematical induction,

7^n-3^n

is divisible by 4 for all integers

n\ge1

Why

Tip: replace the power with the larger base (

7^k

), then the smaller power collects into a multiple of the divisor:

7\cdot3^k-3\cdot3^k=4\cdot3^k

Exam-style · Induction, then an application

Slide 9

(i) Prove by induction that for all integers

n\ge1

1\times1!+2\times2!+\dots+n\times n!=(n+1)!-1.

Show answerHide answer

Answer

Step 1.

n=1

: LHS

=1\times1!=1

, RHS

=2!-1=1

. True.
Step 2. Assume true for

n=k

\displaystyle\sum_{r=1}^kr\times r!=(k+1)!-1

.
Step 3. Need to show

\displaystyle\sum_{r=1}^{k+1}r\times r!=(k+2)!-1

. LHS

=(k+1)!-1+(k+1)\times(k+1)!

(by the assumption)

=(k+1)!\,(1+k+1)-1=(k+2)(k+1)!-1=(k+2)!-1=

RHS.
Step 4. Hence, by mathematical induction, the statement is true for all integers

n\ge1

Why

Factorise

(k+1)!

from the first and last terms, then use

(k+2)(k+1)!=(k+2)!

(ii) Hence find the value of

1\times1!+2\times2!+\dots+10\times10!

Show answerHide answer

Answer

11!-1=39\,916\,799

Why

Put

n=10

in the result from (i):

11!=39\,916\,800

Spot the flaw · Induction

Slide 10

A student wrote this. Find the flaw, explain why it matters, then write a correct version.

Claim

$n^2+n+1$ is even for all integers $n\ge1$ .

Assume true for $n=k$ : $k^2+k+1=2M$ for some integer $M$ .
For $n=k+1$ : $(k+1)^2+(k+1)+1=(k^2+k+1)+2k+2=2M+2(k+1)$ .
This is even, so it is true for $n=k+1$ . Hence true for all $n\ge1$ by induction.

Task Find the flaw, explain why it matters, then write a correct version.

Show answerHide answer

Answer

Flaw: there is no base case.

P(1)

gives

1+1+1=3

, which is odd, so the claim is false.
Correct version: prove instead that

n^2+n+1

is odd, directly (since

n(n+1)

is even,

n(n+1)+1

is odd) or by induction starting with

P(1)

3

is odd.

Why

The inductive step is valid (

P(k)\Rightarrow P(k+1)

), but without a true first case it proves nothing, as the chain of implications never starts. Both steps are needed, and the conclusion must name where the induction starts.

Exit ticket

Slide 11

Define $P(n)$ and write a conclusion at each step.

(a) Prove by induction that

4^n+14

is divisible by 6 for all integers

n\ge1

Show answerHide answer

Answer

Let

P(n)

4^n+14

is divisible by 6.
Step 1.

n=1

4+14=18=6\times3

\therefore P(1)

is true.
Step 2. Assume

4^k+14=6M

for some integer

M

, so

4^k=6M-14

.
Step 3.

4^{k+1}+14=4(6M-14)+14=24M-42=6(4M-7)

, divisible by 6.

\therefore P(k+1)

is true whenever

P(k)

is true.
Step 4. Hence, by mathematical induction,

P(n)

is true for all integers

n\ge1

Why

Substitute for

4^k

from the assumption and check every term has a factor of 6.

(b) A student proves that

3^n+7^n

is divisible by 10 for all odd

n

by assuming the result for

n=k

and proving it for

n=k+1

. State what is wrong.

Show answerHide answer

Answer

For odd

n

, the next case after

n=k

n=k+2

, not

k+1

Why

k+1

is even and is not in the set of cases being proved, so the induction never links one odd case to the next. The conclusion must also say “for all odd positive integers

n

”.