Lesson 9 · Further induction III: induction in context

Learning intentionTo apply mathematical induction in a range of contexts: recursive sequences, derivatives, trigonometric identities, the binomial theorem, logarithms and geometry.

Success criteria · I can…

prove a formula for a recursively defined sequence
prove results about derivatives and trigonometric products or sums
prove Pascal’s identity and the binomial theorem by induction
prove logarithm results and simple geometric results by induction

ResourcesLesson slides
Practice worksheet
Worked solutions
Induction Coach applet

Lesson flow

LaunchWarm-up · Part ASlide 2 DefinitionsRecursive sequencesSlide 3 ExamplesExample 2 · A recursive fractionSlide 4 HSC-styleHSC practice · A nested square rootSlide 5 ExamplesExample 3 · Calculus and trigonometrySlide 6 HSC-styleHSC practice · A trigonometric sumSlide 7 ThinkSpot the flaw · What’s missing?Slide 8 LaunchWarm-up · Part BSlide 9 Key ideasThe binomial theorem by inductionSlide 10 ExamplesExample 5 · Induction with logarithmsSlide 11 ExamplesExample 6 · Induction in geometrySlide 12 Exit ticketExit ticketSlide 13

Warm-up · Part A

Slide 2

(a) If

a_1=2

and

a_{n+1}=3a_n-2

, find

a_2

a_3

a_4

Show answerHide answer

Answer

a_2=4

a_3=10

a_4=28

. A pattern:

a_n=3^{n-1}+1

Why

Apply the rule repeatedly:

3(2)-2=4

3(4)-2=10

3(10)-2=28

. These equal

3^1+1

3^2+1

3^3+1

(b) Differentiate

xe^x

, then differentiate the answer again.

Show answerHide answer

Answer

(x+1)e^x

, then

(x+2)e^x

. A pattern:

(x+n)e^x

Why

Product rule:

e^x+xe^x=(x+1)e^x

. Again:

e^x+(x+1)e^x=(x+2)e^x

(c) Write

\sin2A

and

\cos2A

in terms of

\sin A

and

\cos A

Show answerHide answer

Answer

\sin2A=2\sin A\cos A

and

\cos2A=\cos^2A-\sin^2A=2\cos^2A-1=1-2\sin^2A

Why

These are the double angle formulas. The three forms of

\cos2A

come from

\sin^2A+\cos^2A=1

(d) Show that

1+\cos\theta=2\cos^2\dfrac\theta2

Show answerHide answer

Answer

Put

A=\dfrac\theta2

\cos2A=2\cos^2A-1

\cos\theta=2\cos^2\dfrac\theta2-1

, so

1+\cos\theta=2\cos^2\dfrac\theta2

Why

Parts (a), (b) and (d) are all used later in the lesson.

Recursive sequences

Slide 3

Definition

Proving a formula for a recursively defined sequence

A sequence is defined recursively when each term is given in terms of earlier terms, for example $a_1=2$ , $a_{n+1}=3a_n-2$ .

To prove a formula for $a_n$ : check $a_1$ ; assume the formula for $a_k$ ; then substitute it into the recursion to get $a_{k+1}$ .

Example 1

Prove by induction that if

a_1=2

and

a_{n+1}=3a_n-2

, then

a_n=3^{n-1}+1

for all integers

n\ge1

Show answerHide answer

Answer

Let

P(n)

be the statement

a_n=3^{n-1}+1

.
Step 1.

P(1)

3^0+1=2=a_1

, so

P(1)

is true.
Step 2. Assume

P(k)

a_k=3^{k-1}+1

for some integer

k\ge1

.
Step 3.

a_{k+1}=3a_k-2=3\left(3^{k-1}+1\right)-2=3^k+1.

P(k+1)

is true when

P(k)

is true.
Step 4. True for

n=1

, and true for

n=k\Rightarrow n=k+1

, so true for all integers

n\ge1

by induction.

Why

The assumption is used inside the recursion: replace

a_k

a_{k+1}=3a_k-2

by the assumed formula. This differs from series, where you add a term to the assumed sum.

Example 2 · A recursive fraction

Slide 4

Example 2

A sequence is defined by

u_1=1

and

u_{n+1}=\dfrac{u_n}{1+u_n}

. Find

u_2

u_3

u_4

, make a conjecture for

u_n

, and prove it by induction.

Show answerHide answer

Answer

u_2=\dfrac12

u_3=\dfrac13

u_4=\dfrac14

. Conjecture:

u_n=\dfrac1n

.
Step 1.

u_1=1=\dfrac11

.
Step 2. Assume

u_k=\dfrac1k

for some integer

k\ge1

.
Step 3.

u_{k+1}=\frac{u_k}{1+u_k}=\frac{1/k}{1+1/k}=\frac{1/k}{(k+1)/k}=\frac1{k+1}.

Step 4. True for

n=1

, and true for

n=k\Rightarrow n=k+1

, so true for all integers

n\ge1

by induction.

Why

Conjecture first from the pattern, then prove it: this is the reasoning and communication the syllabus asks for. In Step 3, multiply top and bottom of the complex fraction by

k

HSC practice · A nested square root

Slide 5

2022 HSC Q13(b)The sequence

a_n

is defined by

a_1=\sqrt2

and

a_{n+1}=\sqrt{2+a_n}

for

n\ge1

. Prove by induction that

a_n=2\cos\left(\dfrac\pi{2^{n+1}}\right)

for all integers

n\ge1

. You may use

\sqrt{2+2\cos\theta}=2\cos\dfrac\theta2

for

0\le\theta\le\pi

(warm-up (d)).

Show answerHide answer

Answer

Step 1.

P(1)

2\cos\dfrac\pi4=2\times\dfrac{\sqrt2}2=\sqrt2=a_1

, so

P(1)

is true.
Step 2. Assume

a_k=2\cos\dfrac\pi{2^{k+1}}

for some integer

k\ge1

.
Step 3.

a_{k+1}=\sqrt{2+2\cos\frac\pi{2^{k+1}}}=\sqrt{4\cos^2\frac\pi{2^{k+2}}}=2\cos\frac\pi{2^{k+2}},

taking the positive root since

0<\dfrac\pi{2^{k+2}}<\dfrac\pi2

, so the cosine is positive.
Step 4. True for

n=1

, and true for

n=k\Rightarrow n=k+1

, so true for all integers

n\ge1

by induction.

Why

Use the given identity with

\theta=\dfrac\pi{2^{k+1}}

, which lies in

[0,\pi]

. Then

\dfrac\theta2=\dfrac\pi{2^{k+2}}

. The positive square root must be justified:

\sqrt{4\cos^2\phi}=2|\cos\phi|=2\cos\phi

only because

\cos\phi>0

. (Wording adapted from the paper.)

Example 3 · Calculus and trigonometry

Slide 6

Example 3

(a) Prove by induction that

\dfrac{d^n}{dx^n}\left(xe^x\right)=(x+n)e^x

for all integers

n\ge1

Show answerHide answer

Answer

Step 1.

P(1)

\dfrac d{dx}\left(xe^x\right)=e^x+xe^x=(x+1)e^x

.
Step 2. Assume

\dfrac{d^k}{dx^k}\left(xe^x\right)=(x+k)e^x

for some integer

k\ge1

.
Step 3.

\frac{d^{k+1}}{dx^{k+1}}\left(xe^x\right)=\frac d{dx}\left[(x+k)e^x\right]=e^x+(x+k)e^x=(x+k+1)e^x.

Step 4. True for

n=1

, and true for

n=k\Rightarrow n=k+1

, so true for all integers

n\ge1

by induction.

Why

The

(k+1)

th derivative is the derivative of the

k

th derivative. Use the product rule on

(x+k)e^x

, treating

k

as a constant.

(b) Prove by induction that, for

\sin x\ne0

\cos x\cos2x\cos4x\cdots\cos\left(2^{n-1}x\right)=\dfrac{\sin\left(2^nx\right)}{2^n\sin x}

Show answerHide answer

Answer

Step 1.

P(1)

\dfrac{\sin2x}{2\sin x}=\dfrac{2\sin x\cos x}{2\sin x}=\cos x

.
Step 2. Assume the product up to

\cos\left(2^{k-1}x\right)

equals

\dfrac{\sin\left(2^kx\right)}{2^k\sin x}

for some integer

k\ge1

.
Step 3. Multiply by

\cos\left(2^kx\right)

\frac{\sin(2^kx)\cos(2^kx)}{2^k\sin x}=\frac{\tfrac12\sin\left(2^{k+1}x\right)}{2^k\sin x}=\frac{\sin\left(2^{k+1}x\right)}{2^{k+1}\sin x}.

Step 4. True for

n=1

, and true for

n=k\Rightarrow n=k+1

, so true for all integers

n\ge1

by induction.

Why

The

(k+1)

th product is the

k

th product times one new factor,

\cos(2^kx)

. The double angle formula with

A=2^kx

gives

\sin A\cos A=\tfrac12\sin2A

HSC practice · A trigonometric sum

Slide 7

2019 HSC Q14(c)(i) Show that

\cot x-\cot2x=\csc2x

.
(ii) Hence prove by induction that for all integers

n\ge1

\sum_{r=1}^{n}\csc\left(2^rx\right)=\cot x-\cot\left(2^nx\right).

Show answerHide answer

Answer

(i)

\cot x-\cot2x=\frac{\cos x}{\sin x}-\frac{\cos2x}{2\sin x\cos x}=\frac{2\cos^2x-\cos2x}{2\sin x\cos x}=\frac1{\sin2x}=\csc2x.

(ii) Step 1.

P(1)

\csc2x=\cot x-\cot2x

by (i).
Step 2. Assume

\displaystyle\sum_{r=1}^{k}\csc\left(2^rx\right)=\cot x-\cot\left(2^kx\right)

for some integer

k\ge1

.
Step 3. Add

\csc\left(2^{k+1}x\right)=\cot\left(2^kx\right)-\cot\left(2^{k+1}x\right)

, which is (i) with

x

replaced by

2^kx

\sum_{r=1}^{k+1}\csc\left(2^rx\right)=\cot x-\cot\left(2^kx\right)+\cot\left(2^kx\right)-\cot\left(2^{k+1}x\right)=\cot x-\cot\left(2^{k+1}x\right).

Step 4. True for

n=1

, and true for

n=k\Rightarrow n=k+1

, so true for all integers

n\ge1

by induction.

Why

In (i),

\cos2x=2\cos^2x-1

makes the numerator

1

, and

2\sin x\cos x=\sin2x

. The key idea in (ii) is “(i) with

x

replaced by

2^kx

”, which students often miss. (Cosec is written csc here; both are fine. Wording adapted from the paper.)

Spot the flaw · What’s missing?

Slide 8

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

Student’s claim

If $a_1=0$ and $a_{n+1}=\sqrt{2+a_n}$ , then $a_n=2\cos\dfrac\pi{2^n}$ for all $n\ge1$ .

$n=1$ : $2\cos\dfrac\pi2=0=a_1$ . Assume $a_k=2\cos\dfrac\pi{2^k}$ .
$a_{k+1}=\sqrt{2+2\cos\dfrac\pi{2^k}}=\sqrt{4\cos^2\dfrac\pi{2^{k+1}}}=2\cos\dfrac\pi{2^{k+1}}$ .
Hence true for all $n\ge1$ by induction. □

Spot the flawWhat is missing from this proof, and why would a marker deduct for it?

Show answerHide answer

Answer

Nothing written is false, but three things are missing.
1. The step

2+2\cos2\theta=4\cos^2\theta

(from

\cos2\theta=2\cos^2\theta-1

, with

\theta=\dfrac\pi{2^{k+1}}

) is not shown.
2.

\sqrt{4\cos^2\theta}=2|\cos\theta|

, so we must justify

\cos\dfrac\pi{2^{k+1}}>0

. This is true because

0<\dfrac\pi{2^{k+1}}\le\dfrac\pi4<\dfrac\pi2

for

k\ge1

.
3. There is no conclusion naming

P(k+1)

and the start value: “

P(1)

is true, and

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

, so

P(n)

is true for all

n\ge1

by induction.”

Why

Compare the 2022 HSC question earlier in this lesson, which has the same structure with

a_1=\sqrt2

. In an induction proof every step must be justified, in particular the choice of the positive square root, and the conclusion must be stated.

Warm-up · Part B

Slide 9

A fresh start for the second half of the lesson.

(a) Evaluate

\dbinom52+\dbinom53

and

\dbinom63

. What do you notice?

Show answerHide answer

Answer

10+10=20=\dbinom63

Why

This is Pascal’s identity:

\dbinom52+\dbinom53=\dbinom63

(b) Expand

(1+x)^4

using Pascal’s triangle.

Show answerHide answer

Answer

1+4x+6x^2+4x^3+x^4

Why

The row of Pascal’s triangle 1, 4, 6, 4, 1 gives the coefficients.

(c) Simplify

\ln\left(1-\dfrac1{r^2}\right)

as a single log of a product of two fractions.

Show answerHide answer

Answer

\ln\left[\dfrac{r-1}r\times\dfrac{r+1}r\right]

Why

1-\dfrac1{r^2}=\dfrac{r^2-1}{r^2}=\dfrac{(r-1)(r+1)}{r^2}

, which is the product

\dfrac{r-1}r\times\dfrac{r+1}r

. Equivalently

\ln\dfrac{r-1}r+\ln\dfrac{r+1}r

(d) How many diagonals does a hexagon have?

Show answerHide answer

Answer

Why

Each of the 6 vertices joins to 3 non-adjacent vertices, and each diagonal is counted twice:

\dfrac{6\times3}2=9

The binomial theorem by induction

Slide 10

Theorem

Pascal’s identity and the binomial theorem

Pascal’s identity: $\binom k{r-1}+\binom kr=\binom{k+1}r,\qquad 1\le r\le k.$

Binomial theorem: $(1+x)^n=\sum_{r=0}^{n}\binom nrx^r\quad\text{for all integers }n\ge1.$

Pascal’s identity is the key step: it combines the coefficients of $x^r$ from $(1+x)^k\times1$ and $(1+x)^k\times x$ .

Example 4

(a) Prove Pascal’s identity using the factorial formula.

Show answerHide answer

Answer

Using

\dbinom nr=\dfrac{n!}{r!(n-r)!}

\binom k{r-1}+\binom kr=\frac{k!}{(r-1)!(k-r+1)!}+\frac{k!}{r!(k-r)!}=\frac{k!\left[r+(k-r+1)\right]}{r!(k-r+1)!}=\frac{(k+1)!}{r!(k+1-r)!}=\binom{k+1}r.

Why

Use the common denominator

r!(k-r+1)!

. The first fraction needs a factor

r

(since

r!=r\,(r-1)!

) and the second needs

(k-r+1)

(since

(k-r+1)!=(k-r+1)(k-r)!

). The numerator becomes

k!(k+1)

(b) Prove the binomial theorem by induction.

Show answerHide answer

Answer

Step 1.

P(1)

(1+x)^1=1+x=\dbinom10+\dbinom11x

.
Step 2. Assume

(1+x)^k=\displaystyle\sum_{r=0}^{k}\binom krx^r

for some integer

k\ge1

.
Step 3.

(1+x)^{k+1}=(1+x)\sum_{r=0}^{k}\binom krx^r=\sum_{r=0}^{k}\binom krx^r+\sum_{r=0}^{k}\binom krx^{r+1}.

The coefficient of

x^r

for

1\le r\le k

\dbinom kr+\dbinom k{r-1}=\dbinom{k+1}r

by (a). The constant term is

1=\dbinom{k+1}0

and the coefficient of

x^{k+1}

1=\dbinom{k+1}{k+1}

. Hence

(1+x)^{k+1}=\displaystyle\sum_{r=0}^{k+1}\binom{k+1}rx^r

.
Step 4. True for

n=1

, and true for

n=k\Rightarrow n=k+1

, so true for all integers

n\ge1

by induction.

Why

Write out a few terms rather than relying only on the sigma notation: the first sum gives the coefficients of

x^r

and the second sum, shifted along by one power, gives the coefficients of

x^{r}

from

\dbinom k{r-1}

. The binomial theorem was used in Extension 1; this is where it is proved.

Example 5 · Induction with logarithms

Slide 11

Example 5

(a) Given

\ln(ab)=\ln a+\ln b

, prove by induction that for positive

a_1,\dots,a_n

\ln\left(a_1a_2\cdots a_n\right)=\displaystyle\sum_{i=1}^{n}\ln a_i

Show answerHide answer

Answer

Step 1.

P(1)

\ln a_1=\ln a_1

.
Step 2. Assume

\ln\left(a_1\cdots a_k\right)=\displaystyle\sum_{i=1}^{k}\ln a_i

for some integer

k\ge1

.
Step 3.

\ln\left(a_1\cdots a_ka_{k+1}\right)=\ln\left(a_1\cdots a_k\right)+\ln a_{k+1}=\sum_{i=1}^{k}\ln a_i+\ln a_{k+1}=\sum_{i=1}^{k+1}\ln a_i.

Step 4. True for

n=1

, and true for

n=k\Rightarrow n=k+1

, so true for all integers

n\ge1

by induction.

Why

The log law

\ln(ab)=\ln a+\ln b

is applied with

a=a_1\cdots a_k

and

b=a_{k+1}

. Then the assumption replaces

\ln(a_1\cdots a_k)

(b) Prove by induction that for all integers

n\ge2

\displaystyle\sum_{r=2}^{n}\ln\left(1-\frac1{r^2}\right)=\ln\left(\frac{n+1}{2n}\right)

Show answerHide answer

Answer

Step 1.

P(2)

\ln\left(1-\dfrac14\right)=\ln\dfrac34=\ln\dfrac{3}{2\times2}

, true.
Step 2. Assume the result for some integer

k\ge2

.
Step 3.

\sum_{r=2}^{k+1}\ln\left(1-\frac1{r^2}\right)=\ln\frac{k+1}{2k}+\ln\left(1-\frac1{(k+1)^2}\right)=\ln\left[\frac{k+1}{2k}\times\frac{k(k+2)}{(k+1)^2}\right]=\ln\frac{k+2}{2(k+1)}.

Step 4. True for

n=2

, and true for

n=k\Rightarrow n=k+1

, so true for all integers

n\ge2

by induction.

Why

The starting value is

n=2

. Use

1-\dfrac1{(k+1)^2}=\dfrac{(k+1)^2-1}{(k+1)^2}=\dfrac{k(k+2)}{(k+1)^2}

. A non-induction method is to telescope using warm-up (c).

Example 6 · Induction in geometry

Slide 12

Think: when a new vertex is added between two neighbouring vertices, which new diagonals appear?

Example 6

Prove by induction that a convex polygon with

n

sides has

\dfrac{n(n-3)}2

diagonals, for all integers

n\ge3

Show answerHide answer

Answer

Step 1.

P(3)

: a triangle has 0 diagonals and

\dfrac{3\times0}2=0

.
Step 2. Assume a convex

k

-gon has

\dfrac{k(k-3)}2

diagonals, for some integer

k\ge3

.
Step 3. Add a vertex

V

outside the edge

AB

to make a convex

(k+1)

-gon. The new diagonals are

V

joined to the

k-2

vertices other than

A

and

B

, and the old side

AB

is now a diagonal:

k-1

new diagonals.

\frac{k(k-3)}2+k-1=\frac{k^2-k-2}2=\frac{(k+1)(k-2)}2=\frac{(k+1)\big((k+1)-3\big)}2.

Step 4. True for

n=3

, and true for

n=k\Rightarrow n=k+1

, so true for all integers

n\ge3

by induction.

Why

In a geometry proof, Step 3 must say in words what the

(k+1)

th step adds. Draw a hexagon becoming a heptagon:

V

is adjacent only to

A

and

B

, so it makes diagonals to the other

k-2

vertices, and

AB

stops being a side.

Exit ticket

Slide 13

A sequence is defined by

a_1=5

and

a_{n+1}=2a_n-3

. Prove by induction that

a_n=2^n+3

for all integers

n\ge1

Show answerHide answer

Answer

Step 1.

P(1)

2+3=5=a_1

, so

P(1)

is true.
Step 2. Assume

a_k=2^k+3

for some integer

k\ge1

.
Step 3.

a_{k+1}=2a_k-3=2\left(2^k+3\right)-3=2^{k+1}+3

. So

P(k+1)

is true when

P(k)

is true.
Step 4. True for

n=1

, and true for

n=k\Rightarrow n=k+1

, so true for all integers

n\ge1

by induction.

Why

Substitute the assumption into the recursion. Do not use the formula for

a_{k+1}

in Step 3, as that is what you are proving. Check:

a_2=7=2^2+3