# Proof by induction

• Mar 2nd 2010, 04:59 AM
thatsphatt
Proof by induction
So, I do this at sixth form, but in further maths, so I guess it's closer to Uni maths than 'pre-college' work.

I'm really stuck, I can't even work out my base step for this proof properly!

Prove that the general term of the sequence described by
U(n+1) = 3U(n) + 4, n E Z+
is U(n) = 3^n - 2 n E Z+

where u(1) = 1

Normally, on the divisibility and series ones we've done, the base step is n=1, but I can't see how that's going to help me with this?!
• Mar 2nd 2010, 05:50 AM
Quote:

Originally Posted by thatsphatt
So, I do this at sixth form, but in further maths, so I guess it's closer to Uni maths than 'pre-college' work.

I'm really stuck, I can't even work out my base step for this proof properly!

Prove that the general term of the sequence described by
U(n+1) = 3U(n) + 4, n E Z+
is U(n) = 3^n - 2 n E Z+

where u(1) = 1

Normally, on the divisibility and series ones we've done, the base step is n=1, but I can't see how that's going to help me with this?!

Hi thatsphatt,

it seems that U(1)=1 is a missing piece of information.

Then, using

$\displaystyle U_{n+1}=3U_n+4$

$\displaystyle U_1=1$

$\displaystyle U_2=3(1)+4=7=3^1-2$

$\displaystyle U_3=3(7)+4=25=3^3-2$

$\displaystyle U_4=3(25)+4=79=3^4-2$

and so on...

Therefore

F(k)

$\displaystyle U_{k}=3^k-2$

F(k+1)

$\displaystyle U_{k+1}=3^{k+1}-2$

$\displaystyle 3^{k+1}-2=(3)3^k-2=3\left(3^k-2\right)-2+6=3(U_k)+4$

This means the formulation being true for n=1 causes the formulation to be true for n=2,
causing true for n=3, causing....... an infinite chain of cause and effect.

Test for n=1

$\displaystyle U_2=3(1)+4=7$

$\displaystyle U_2=3^2-2=9-2=7$

Therefore, the nth term, in terms of n only is

$\displaystyle U_n=3^n-2$
• Mar 2nd 2010, 06:01 AM
thatsphatt
Oh I see!
I think I'll be able to write down what I need from that!
Thank you :)