Induction and Recursion I have NO idea

[1MileCrash]

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

Induction and recursion is mercilessly whooping my ***.

Homework Statement

Let a₁ = 1. For each natural number n > 1, let a_n = 3a_n-1 - 1.

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

Homework Equations

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?

 

[1MileCrash]

I think I see..

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

And based on my assumption, a_n = 1/2(3<sup>n-1[/SUP + 1)

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

Am I on the right track?</sup>

 

[micromass]

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

 

[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?

 

[micromass]

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?

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

 

[1MileCrash]

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

 

[micromass]

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

Yes, check it for n=2 of course.

 

[1MileCrash]

Ok, got it. Thanks again!