Register to reply 
Induction and Recursion.. I have NO idea! 
Share this thread: 
#1
Mar812, 06:14 PM

P: 1,305

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_{n1}  1. Prove that for each natural number n, a_{n} = 1/2(3^{n1} + 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
Mar812, 06:56 PM

P: 1,305

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]n1[/SUP + 1) So I can plug it in, and algebraically show that a_{n+1} equals 1/2(3[SUP]n[/SUP + 1) Am I on the right track? 


#4
Mar812, 06:58 PM

P: 1,305

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? 


#5
Mar812, 07:01 PM

Mentor
P: 18,346




Register to reply 
Related Discussions  
Need help creating a recursive script in matlab that can do this:  Math & Science Software  1  
Recursion in C  Programming & Computer Science  12  
Function is F(n) = n(n+1)  General Math  4  
C++ fun with recursion  Computing & Technology  17  
What is the largest number of pieces you can get by cutting a pizza  Introductory Physics Homework  1 