My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
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 ?
Jet1045 is offline  
 
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:



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?
johnr is offline  
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?!
Jet1045 is offline  
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!
johnr is offline  
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 ;(
Jet1045 is offline  
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.
Hedge is offline  
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:

icemanfan is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2019 My Math Forum. All rights reserved.