Question

Show by mathematical induction that a_n= 13/5(4ⁿ) + 12/5 (-1)ⁿ for n >= 0, given that

a_n= 3_n-1 + 4a_n-2, a₀ =5, a₁ = 8

Answer 1

The base case is when n=2, so using the given formula we get:

a₂=3a₁+4a₀=24+20=44.

Using the proposed formula we get:

(13/5)(16)+(12/5)(1)=(208+12)/5=220/5=44. The base case holds.

According to the proposed formula, the sum of two consecutive terms of the series causes (12/5)(-1)ⁿ to cancel out:

a_n+a_n+1=(13/5)4ⁿ+(12/5)(-1)ⁿ+(13/5)4ⁿ⁺¹+(12/5)(-1)ⁿ⁺¹,

a_n+a_n+1=(13/5)4ⁿ(1+4)=13(4ⁿ), or a_n=13(4^n-1)-a_n-1 in general terms.

But, according to the recurrence formula:

a_n+a_n+1=3a_n-1+4a_n-2+3a_n+4a_n-1=3a_n+7a_n-1+4a_n-2=3(3a_n-1+4a_n-2)+7a_n-1+4a_n-2,

a_n+a_n+1=16(a_n-1+a_n-2). Applying this for n=2: a₂+a₃=16(a₁+a₀)=4²(8+5)=4²(13)=208. The formula allows us to take consecutive pairs of terms and predict the sum of the next pair.

The series is: 5, 8, 44, 164, ... according to the recursive formula.

If we take the sum of consecutive terms in order we get: 13, 52, 208, ...

This can be written: 13(4⁰), 13(4¹), 13(4²), ...

a₁=8=13(4⁰)-5=13(4⁰)-a₀, a₂=44=13(4¹)-8=44=13(4¹)-a₁, a₃=164=13(4²)-44=13(4²)-a₂, ... 

Note that the third sum is 13(4²)=208, which concurs with the formula derived from the given recursive formula as applied to sums of consecutive pairs. This could indicate that the second sum is 13(4)=52. (The fifth sum would be 4²(4²(13))=4⁴(13), and the fourth sum could then be 4³(13). We could then speculate the nature of the proposed formula.) We have yet to determine the full proposed formula.

From the proposed formula:

a_n+1+a_n=13(4ⁿ⁺¹); a_n-1+a_n-2=13(4^n-1), so a_n+1+a_n=16(a_n-1+a_n-2) as confirmed earlier using the recursive formula (because 4ⁿ⁺¹/4^n-1=4²=16).

Consider 4 consecutive terms in the series: a_n, a_n+1, a_n+2, a_n+3.

a_n+2+a_n+3=16(a_n+a_n+1); a_n+2=3a_n+1+4a_n; a_n+3=3a_n+2+4a_n+1; using the given recursive formula.

Therefore, substituting for a_n+2, a_n+3=3(3a_n+1+4a_n)+4a_n+1=13a_n+1+12a_n.

Using the proposed formula:

a_n+3=(13/5)4ⁿ⁺³+(12/5)(-1)ⁿ⁺³; a_n+1=(13/5)4ⁿ⁺¹+(12/5)(-1)ⁿ⁺¹; a_n=(13/5)4ⁿ+(12/5)(-1)ⁿ.

13a_n+1=13((13/5)4ⁿ⁺¹+(12/5)(-1)ⁿ⁺¹)=13(52/5)4ⁿ-13(12/5)(-1)ⁿ;

12a_n=12((13/5)4ⁿ+(12/5)(-1)ⁿ)=12(13/5)4ⁿ+12(12/5)(-1)ⁿ.

13a_n+1+12a_n=(64×13/5)4ⁿ-(12/5)(-1)ⁿ=(13/5)4ⁿ⁺³+(12/5)(-1)ⁿ, which is the expression for a_n+3 using the proposed formula. Note that (-1)ⁿ⁺³=(-1)ⁿ(-1)³=-(-1)ⁿ, hence the change of sign.

By induction then, we have the proof of the proposed formula.