# Mathematical Induction Problem

• Apr 6th 2011, 12:28 PM
Kostapoulous
Mathematical Induction Problem
Ok guys, I really need help with this, I can understand almost everything in my class except induction. Can someone please help me with a solution to the following problem?

Use mathematical induction to show that

$\displaystyle F(n) = 3 × 2^{n-1}\ -2$

is the solution for the recurrence relation:

T(n) = 2T(n–1) + 2 for n > 1 and T(1) = 1

Thanks in advance for any help supplied.
• Apr 6th 2011, 01:36 PM
Quote:

Originally Posted by Kostapoulous
Ok guys, I really need help with this, I can understand almost everything in my class except induction. Can someone please help me with a solution to the following problem?

Use mathematical induction to show that

$\displaystyle F(n) = 3 × 2^{n-1}\ -2$

is the solution for the recurrence relation:

T(n) = 2T(n–1) + 2 for n > 1 and T(1) = 1

Thanks in advance for any help supplied.

P(k) is

$\displaystyle F(k)=(3)2^{k-1}-2$

P(k+1) is

$\displaystyle F(k+1)=(3)2^k-2$

Try to show that P(k) "being true" forces P(k+1) to also be true.

$\displaystyle F(k+1)=[2]F(k)+2$

which, if P(k) is true, is

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

Have a shot at the base case.