Mathematical Induction

**wir3d_riot** · March 29th 2009, 02:31 PM

Hi there,

I'm totally dumbfounded by this question. Could anyone give me a basis on where to start so I can at least try to work it out myself?

Use mathematical induction to show that:

$S(n) = 3*2^{n-1} -2$

is the solution for the reccurence relation:

$T(n)=2T(n-1)+2$ for $n > 1$ and $T(1) = 1$

**halbard** · March 29th 2009, 03:10 PM

To prove $T(n)=S(n)$ for all positive integers $n$ all you have to do is show

(i) that $T(1)=S(1)$ , and
(ii) that if $T(k-1)=S(k-1)$ for some $k>1$ then also $T(k)=S(k)$ for that very same $k$ .

Here we go.

Let $S(n)=3\times2^{n-1}-2$ .

Initial step: $S(1)=3\times2^0-2=3-2=1$ , so $T(1)=S(1)$ .

Inductive step: Assume that $T(k-1)=S(k-1)$ for some $k>1$ .

Then $T(k)=2T(k-1)+2=2S(k-1)+2=2(3\times2^{k-2}-2)+2=3\times2^{k-1}-2=S(k)$ .

Thus, by the principle of induction, $T(n)=S(n)$ for all positive integers $n$ .

**wir3d_riot** · March 29th 2009, 03:40 PM

Thanks, that helped a lot. I have a follow up question here.

If 1 is added to the recurrence relation such that:

$T(n) = 2T(n-1) + 3$ for $n > 1$ and $T(1) = 0$

What is the new equation for S(n)?
Prove it by induction.

Am I basically reversing the steps in the first answer to come up with a new equation for S(n)? This is what I've come up with:

$T(k) = 2T(k-1)+3=2S(k-1)+3=3(3*2^{k-2}-2)+3=3x2^{k-1}-3=S(k)$

Thread: Mathematical Induction

LinkBack

Thread Tools

Display