Which recurrence relation is greater?

In summary, the given equations are increasing functions starting with positive integers and involving only addition. Therefore, the function with B has a greater initial value and is greater than the function with A. This is true unless the rate at which A is increasing is greater than the rate at which B is increasing. However, it is possible to find a direct formula for A and B using c-values and exponents, as shown by the professor's solution. By comparing the values of the exponents and the c-values, it is determined that An is greater than Bn for all values of n, as long as the given conditions hold.
  • #1
swtlilsoni
16
0

Homework Statement


An+2=6An+1+6An
A1=A2=1
Bn+2=5Bn+1+9Bn
B1=B2=10100

a) is it true that Bn>An for every integer n > 0?
b) is it true that Bn>An for infinetly many integers n>0?


The Attempt at a Solution



It just seems like these are increasing functions since they both start with positive integers and are only addition. Thus the function with B has a greater initial value so it should be greater.
The only way this wouldn't be true is if the rate at which A is increasing is greater than the rate at which B is increasing.
However I do not know how to find the rate.
 
Physics news on Phys.org
  • #2
Probably there is some nice trick for this, but personally I would try solving for the direct formula (for inspiration, check wikipedia)
 
  • #3
Here is what my professor wrote (I don't completely understand what he did):
An= c1[tex]\alpha[/tex]n + c2[tex]\beta[/tex]n
c1,c2= 3 [tex]\pm[/tex] [tex]\sqrt{}15[/tex]
Bn= c3[tex]\delta[/tex]n + c4[tex]\varpi[/tex]n
c3,c4= (5 [tex]\pm[/tex] [tex]\sqrt{}61[/tex])/2

3+[tex]\sqrt{}15[/tex]=[tex]\alpha[/tex]=6.8
3-[tex]\sqrt{}15[/tex]=.9n = approaching zero
(5 + [tex]\sqrt{}61[/tex])/2 = [tex]\delta[/tex] = 6.5
(5 - [tex]\sqrt{}61[/tex])/2 = [tex]\varpi[/tex] = -1.5

An > Bn for all n
since [tex]\alpha[/tex] > [tex]\delta[/tex] > [tex]\varpi[/tex]

I have NO CLUE how he got this. It is possible I could have copied some of it wrong, but this is the general idea of what he did. I'm sure it could be helpful in figuring out how this problem should be done?
 

FAQ: Which recurrence relation is greater?

1. What is a recurrence relation?

A recurrence relation is a mathematical equation or formula that describes the relationship between a sequence of numbers, where each term is defined in terms of one or more of the previous terms.

2. How do you determine which recurrence relation is greater?

The comparison of recurrence relations typically involves analyzing the behavior of each relation as the input values increase. This can be done by finding the closed-form expression, or by using techniques such as induction or substitution to compare the growth rates of the two relations.

3. What factors affect the comparison of recurrence relations?

The main factors that affect the comparison of recurrence relations are the coefficients, exponents, and initial conditions of each relation. These factors determine the growth rate and behavior of the sequence of numbers generated by each relation.

4. Can two recurrence relations be equal?

Yes, it is possible for two recurrence relations to be equal. This can occur when both relations have the same coefficients, exponents, and initial conditions, resulting in the same sequence of numbers being generated.

5. How is the comparison of recurrence relations used in real-world applications?

The comparison of recurrence relations is used in a variety of fields, such as computer science, engineering, and economics, to analyze the performance and efficiency of algorithms, predict growth rates in data sets, and model real-world phenomena.

Back
Top