# Induction and Recursion.. I have NO idea!

by 1MileCrash
Tags: induction, recursion
 Share this thread:
 P: 1,302 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?
 P: 1,302 I think I see.. I know that an+1 = 3an - 1 because that's the definition. And based on my assumption, an = 1/2(3[SUP]n-1[/SUP + 1) So I can plug it in, and algebraically show that an+1 equals 1/2(3[SUP]n[/SUP + 1) Am I on the right track?
 Mentor P: 18,290 Yes, that's the idea. Can you do that?
 P: 1,302 Induction and Recursion.. I have NO idea! 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?
Mentor
P: 18,290
 Quote by 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?
Yes, you only need to show it's true for n=1 and you need to show the induction step.
 P: 1,302 Do you mean n = 2? If n = 1, an-1 is undefined?
Mentor
P: 18,290
 Quote by 1MileCrash Do you mean n = 2? If n = 1, an-1 is undefined?
Yes, check it for n=2 of course.
 P: 1,302 Ok, got it. Thanks again!

 Related Discussions Math & Science Software 1 Programming & Computer Science 12 General Math 4 Computing & Technology 17 Introductory Physics Homework 1