A mistake in using Mathematical Induction

Question

A sequence of real numbers {a_n} is defined as follows:

a₀ = a₁ = 1, a₂ = 3 and

a_n+3 = 3a_n+2 – a_n+1 – 2a_n where n = 0, 1, 2, …

Let b_k = a_k+2 – a_k+1 – a_k , where k = 0, 1, 2, …

Prove that b_n = 2b_n-1 " n Î N .

‘Solution’

Find the conceptual mistake in the following proof:

Let P(n) be the proposition : b_n = 2b_n-1

For P(1),

b₀ = a₂ – a₁ – a₀ = 3 – 1 – 1 = 1

b₁ = a₃ – a₂ – a₁ = (3a₂ – a₁ – 2a₀) – a₂ – a₁ = 2(a₂ – a₁ – a₀)

= 2(3 – 1 – 1) = 2

\ b₁ = 2b₀ .

\ P(1) is true.

Assume P(k) is true for some kÎ N, that is,

b_k = 2b_k-1 (*)

For P(k + 1),

b_k+1 = a_k+3 – a_k+2 – a_k+1

= (3a_k+2 – a_k+1 – 2a_k) – a_k+2 – a_k+1

= 2(a_k+2 – a_k+1 – a_k)

= 2b_k

\ P(k + 1) is true.

By the Principle of Mathematical Induction, P(n) is true " n Î N.

The Mistake

In the proof of P(k + 1) above, there is no where in which the inductive hypothesis, that is, (*) is used.

In fact, the proof does not need to use Mathematical Induction at all.

Just write,

b_n = a_n+2 – a_n+1 – a_n

= (3a_n+1 – a_n – 2a_n-1) – a_n+1 – a_n

= 2(a_n+1 – a_n – a_n-1)

= 2b_n-1

The proof is already completed.

Exercise

If you insist to use mathematical induction, the proof of

P(k + 1) above should be changed in order that (*) is used.

It will be quite tedious to write the proof out, can you do this ?