
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
April 1st, 2013, 03:43 PM  #1 
Senior Member Joined: Jan 2012 Posts: 118 Thanks: 1  Recurrence Relations & Induction
Hello there. Have a quick question. A problem says to : Show that: is a recurrence relation for an. This may be an extremely simple question but I barely understand this whole recurrence relation and induction stuff. Would I use induction here ? 
April 1st, 2013, 07:38 PM  #2  
Math Team Joined: Apr 2012 Posts: 1,579 Thanks: 22  Re: Recurrence Relations & Induction Quote:
So what does A_4 equal?  
April 2nd, 2013, 09:55 AM  #3 
Senior Member Joined: Jan 2012 Posts: 118 Thanks: 1  Re: Recurrence Relations & Induction
thanks! ya i totally get that. Like i understand how to get all of the next terms in the sequence. But if its asking to show, is that all you would do then?!

April 2nd, 2013, 10:46 AM  #4  
Math Team Joined: Apr 2012 Posts: 1,579 Thanks: 22  Re: Recurrence Relations & Induction Quote:
These sequences are fun to work with and of some real importance in number theory. Happy adventuring!  
April 2nd, 2013, 09:11 PM  #5 
Senior Member Joined: Jan 2012 Posts: 118 Thanks: 1  Re: Recurrence Relations & Induction
Okay Great! Yeah I just expected that maybe he would want us to show more, but hopefully that's fine. I'll just show the relation but giving the next couple values. Heres one i'm having trouble with. Using strong induction show that: is a solution to the recurrence relation from part a. Part a being the recurrence relation I posted above. I HAVE NO CLUE WHERE TO START, mainly because I don't understand strong induction because he barely explained it. So with strong induction you start with the inductive step opposed to the base case correct? For our example in class he showed that Pn was equal to P(n+4). So i'm confused, do we just pick a random integer. Could I insert n+4 into this equation? I just don't get it ;( 
April 3rd, 2013, 04:41 AM  #6 
Senior Member Joined: Mar 2012 Posts: 572 Thanks: 26  Re: Recurrence Relations & Induction
I'm not sure this will help, but my first step confronted with that would be to pick a couple of terms that are in the series such as a_3 and a_4, then plug them into the equation to see how it works. Firstly this will confirm it does indeed work. Secondly it might give you a clue as to why it works, which could be a start. 
April 3rd, 2013, 11:41 AM  #7 
Senior Member Joined: Feb 2012 Posts: 628 Thanks: 1  Re: Recurrence Relations & Induction
You have to use strong induction to solve this. Strong induction allows you to assume that the statement is true for all n less than or equal to k. Now, the first step is to demonstrate that and according to the formula. Now, if this is true, the first part of the induction proof is done. Then all you have to do is show that the formula for satisfies the recurrence relation . In this case, you must show: 

Tags 
induction, recurrence, relations 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
More Recurrence Relations  roguebyte  Applied Math  1  April 24th, 2012 12:49 AM 
Recurrence Relations  eulerrules1  Computer Science  1  November 10th, 2011 03:38 AM 
recurrence relations  emosms  Applied Math  1  April 22nd, 2011 03:52 AM 
Solving recurrence relations with two variables  mrbobbles  Applied Math  1  May 9th, 2009 11:28 AM 
Recurrence relations  cknapp  Applied Math  0  December 12th, 2007 10:28 AM 