How to Prove a Sequence by Induction

[silina01]

Define the sequence of integers a₁, a₂, a₃,... as follows:
a₁ = 3
a₂ = 6
a_n = 5a_n-1 - 6a_n-2 + 2 for all n ≥ 3
Prove that a_n = 1 + 2^n-1 + 3^n-1

------------------------------------------------------------------------------------------------
my attempt:
base case:
n=1
1+ 2⁰ +3⁰
= 1
= a₁
therefore n=1 holds

n=2
1+ 2¹ +3¹
= 6
= a₂
therefore n=2 holds

Assume k holds for all k > n, n≥3 then

a_n = 5a_n-1 - 6a_n-2 + 2
= 5(1+2^n-2 + 3^n-2) -6(1 + 2^n-3+ 3^n-3) +2
= 1 + 10^n-2 + 15^n-2 -12^n-3 -18^n-3

I have no idea what to do from here.

 

[eumyang]

Assume k holds for all k > n, n≥3 then

a_n = 5a_n-1 - 6a_n-2 + 2
= 5(1+2^n-2 + 3^n-2) -6(1 + 2^n-3+ 3^n-3) +2
= 1 + 10^n-2 + 15^n-2 - 12^n-3 - 18^n-3

$5 \cdot 2^{n-2} \ne 10^{n-2}$
$5 \cdot 3^{n-2} \ne 15^{n-2}$
...and so on.

I don't know if this will help, but note that
$2^{n-2} = 2\cdot 2^{n-3}$
and
$3^{n-2} = 3\cdot 3^{n-3}$

 

[Mentallic]

= 5(1+2^n-2 + 3^n-2) -6(1 + 2^n-3+ 3^n-3) +2
= 1 + 10^n-2 + 15^n-2 -12^n-3 -18^n-3

Your second line is incorrect.

$$a\cdot b^n = a^1b^n \neq (ab)^n = a^nb^n$$

 

[silina01]

okay, but I am still stuck

 

[eumyang]

Best I can do is give you some other examples that use the properties that you may need to continue:
$4(2+5^{n-3}) = 8 + 4 \cdot 5^{n-3}$
$-7 \cdot 4^{n-1} = -7 \cdot 4 \cdot 4^{n-2} = -28 \cdot 4^{n-2}$
$12 \cdot 10^{n-5} - 4 \cdot 10^{n-5} = 8 \cdot 10^{n-5}$

Study the above and try your problem again.


(Mods: hope I am not giving too much away here.)

 

[haruspex]

okay, but I am still stuck

Please post your corrected working, as far as it goes. (Maybe you still have a wrong equation.)

 

[silina01]

I found the answer, thank you all so much!