# Homework Help: Induction and Recursion I have NO idea!

1. Mar 8, 2012

### 1MileCrash

I think I'm pretty good at standard induction. Never had a problem.

Induction and recursion is mercilessly whooping my ***.

1. The problem statement, all variables and given/known data

Let a1 = 1. For each natural number n > 1, let an = 3an-1 - 1.

Prove that for each natural number n, an = 1/2(3n-1 + 1)

2. Relevant equations

3. The attempt at a solution

WAT

I can "build it." And I don't even feel comfortable doing that. Let S be the set of n for which the theorem holds.

Let n = 2

Theorem holds.

Let n = 3

Theorem holds.

So 2,3 are elements of S.

(Do I have to show it for 2? Or more? Or just one? Why?)

Suppose that n >= 3 and {1,2,....,n} is a subset of S.

I have no idea what to do. At all. Can someone please explain recursion induction to me?

2. Mar 8, 2012

### 1MileCrash

I think I see..

I know that
an+1 = 3an - 1 because that's the definition.

And based on my assumption, an = 1/2(3n-1[/SUP + 1)

So I can plug it in, and algebraically show that an+1 equals 1/2(3n[/SUP + 1)

Am I on the right track?

3. Mar 8, 2012

### micromass

Yes, that's the idea. Can you do that?

4. Mar 8, 2012

### 1MileCrash

Yes, that's what I tried and it worked out.

So for this example, I'd really only need to show it to be true for one value, right?

5. Mar 8, 2012

### micromass

Yes, you only need to show it's true for n=1 and you need to show the induction step.

6. Mar 8, 2012

### 1MileCrash

Do you mean n = 2? If n = 1, an-1 is undefined?

7. Mar 8, 2012

### micromass

Yes, check it for n=2 of course.

8. Mar 8, 2012

### 1MileCrash

Ok, got it. Thanks again!