Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

## #1 2013-03-19 05:26:40

genericname
Full Member

Offline

### Proof by induction question

Hi, I am stuck on the last step. What am I supposed to do now?

Problem: Let T(n)=3T(n-1)+2, T(1)=2. Prove by induction that T(n)=3^(n-1)

Here is what I have so far:

Show base case k=1: T(1) = 3^1 - 1 = 2

Show for k=n-1: T(n-1) = (3^((n-1)-1)) -1

Show for k=n :
3((3^(n-2)) - 1) + 2

Last edited by genericname (2013-03-19 05:30:38)

## #2 2013-03-19 05:57:34

stapel
Member

Offline

### Re: Proof by induction question

#### genericname wrote:

Hi, I am stuck on the last step. What am I supposed to do now?

Problem: Let T(n)=3T(n-1)+2, T(1)=2. Prove by induction that T(n)=3^(n-1)

Here is what I have so far:

Show base case k=1: T(1) = 3^1 - 1 = 2

If T(1) = 2 and if the proposed formula is as you've posted, then T(n) for n = 1 is 3^(1-1) = 3^(0) = 1, not 2. So the base step fails.

You appear, in your work, to have used a different formula from that which was proposed. Is there perhaps a typo somewhere?

## #3 2013-03-19 05:58:42

bob bundy
Moderator

Offline

### Re: Proof by induction question

hi genericname

k=1

But you want T(1) = 2 ???

Let's see what is happening here.

term to term rule:

so if T(1) = 2

T(2) = 3x2 + 2 = 8
T(3) = 3x8 + 2 = 26
T(4) = 3x26 + 2 = 80
........................

So did you mean

Try again k=1

That's better.

Now for the induction step

assume

use the term to term rule

This has the right form, so the induction step is complete.

Bob

Last edited by bob bundy (2013-03-19 06:03:25)

You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

## #4 2013-03-19 06:29:27

genericname
Full Member

Offline

### Re: Proof by induction question

Oops, it was a typo. Sorry! It was supposed to be (3^n)-1 like what Bob said.

How did you get rid of the n-1 in that step?

Last edited by genericname (2013-03-19 06:29:47)

## #5 2013-03-19 08:20:13

bob bundy
Moderator

Offline

### Re: Proof by induction question

It's just a matter of multiplying out the bracket( by 3)

Bob

You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

## #6 2013-03-19 15:38:32

genericname
Full Member

Offline

### Re: Proof by induction question

Multiplying out the bracket? Sorry, think I might be misunderstanding something, but wouldn't that be (9^(n-1)) - 3 + 2 if you multiply by 3?

Last edited by genericname (2013-03-19 15:45:17)

## #7 2013-03-19 18:13:02

bob bundy
Moderator

Offline

### Re: Proof by induction question

If you times by another 3 you just increaase the power by 1 ie (n-1) becomes n.

Bob

You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

## #8 2013-03-20 02:16:51

genericname
Full Member

Offline

### Re: Proof by induction question

Oh, I see. Thank you, bob.