My Math Forum Recurrence Relations & Induction

 Number Theory Number Theory Math Forum

 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: $$a_{1}= 3$$ $$a_{2}= 8$$ $$a_{n}= 2a_{n-1} + 2a_{n-2}$$ 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:
 Originally Posted by Jet1045 Hello there. Have a quick question. A problem says to : Show that: $$a_{1}= 3$$ $$a_{2}= 8$$ $$a_{n}= 2a_{n-1} + 2a_{n-2}$$ 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 ?
Ok, so A_3 = 2(A_1+A_2) = 2(3+ = 22

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:
 Originally Posted by Jet1045 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?!
Yes, the value of every number depends on the values of the immediately prior two numbers and the formula for combining them.

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: $a_{n}=\frac{(1 + \sqrt{3})^{n+2} - (1-\sqrt{3})^{n+2}}{4\sqrt{3}}$ 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 $a_1= 3$ and $a_2= 8$ 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 $a_n$ satisfies the recurrence relation $a_n= 2a_{n-1} + 2a_{n-2}$. In this case, you must show: $\frac{(1 + \sqrt{3})^{n+2} - (1 - \sqrt{3})^{n+2}}{4 \sqrt{3}}= 2 \left(\frac{(1 + \sqrt{3})^{n+1} - (1 - \sqrt{3})^{n+1}}{4 \sqrt{3}}\right) + 2 \left(\frac{(1 + \sqrt{3})^{n} - (1 - \sqrt{3})^{n}}{4 \sqrt{3}}\right)$

 Tags induction, recurrence, relations

 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top