Homework Help: Proof by induction sequence

1. Feb 10, 2014

silina01

Define the sequence of integers a1, a2, a3,.... as follows:
a1 = 3
a2 = 6
an = 5an-1 - 6an-2 + 2 for all n ≥ 3
Prove that an = 1 + 2n-1 + 3n-1

------------------------------------------------------------------------------------------------
my attempt:
base case:
n=1
1+ 20 +30
= 1
= a1
therefore n=1 holds

n=2
1+ 21 +31
= 6
= a2
therefore n=2 holds

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

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

I have no idea what to do from here.

Last edited: Feb 10, 2014
2. Feb 10, 2014

eumyang

$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}$

3. Feb 10, 2014

Mentallic

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

4. Feb 11, 2014

silina01

okay, but I am still stuck

5. Feb 11, 2014

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.)

6. Feb 11, 2014

haruspex

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

7. Feb 11, 2014

silina01

I found the answer, thank you all so much!

Last edited: Feb 11, 2014