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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**genericname****Member**- Registered: 2012-05-16
- Posts: 52

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-18 06:30:38)*

Offline

**stapel****Member**- Registered: 2006-07-22
- Posts: 15

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?

Offline

**bob bundy****Administrator**- Registered: 2010-06-20
- Posts: 8,082

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-18 07:03:25)*

Children are not defined by school ...........The Fonz

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

Offline

**genericname****Member**- Registered: 2012-05-16
- Posts: 52

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-18 07:29:47)*

Offline

**bob bundy****Administrator**- Registered: 2010-06-20
- Posts: 8,082

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

Bob

Children are not defined by school ...........The Fonz

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

Offline

**genericname****Member**- Registered: 2012-05-16
- Posts: 52

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-18 16:45:17)*

Offline

**bob bundy****Administrator**- Registered: 2010-06-20
- Posts: 8,082

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

Bob

Children are not defined by school ...........The Fonz

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

Offline

**genericname****Member**- Registered: 2012-05-16
- Posts: 52

Oh, I see. Thank you, bob.

Offline

Pages: **1**