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 a_{1} = 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) 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?
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^{n-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?}
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?