Which recurrence relation is greater?

Click For Summary
SUMMARY

The discussion centers on the comparison of two recurrence relations: An+2=6An+1+6An with initial conditions A1=A2=1, and Bn+2=5Bn+1+9Bn with initial conditions B1=B2=10100. The conclusion drawn is that An is greater than Bn for all integers n > 0, based on the derived growth rates where α (approximately 6.8) is greater than δ (approximately 6.5) and both are greater than the negative root of Bn. This indicates that despite B's larger initial values, A's growth rate surpasses that of B.

PREREQUISITES
  • Understanding of recurrence relations and their properties
  • Familiarity with characteristic equations and roots in linear algebra
  • Knowledge of asymptotic analysis and growth rates
  • Basic skills in solving differential equations
NEXT STEPS
  • Study the derivation of characteristic equations for recurrence relations
  • Learn about asymptotic notation and its application in analyzing growth rates
  • Explore the concept of generating functions for solving recurrence relations
  • Investigate the application of the Master Theorem in analyzing recursive algorithms
USEFUL FOR

Mathematicians, computer scientists, and students studying algorithms or discrete mathematics who are interested in understanding the behavior of recurrence relations and their comparative growth rates.

swtlilsoni
Messages
16
Reaction score
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
Probably there is some nice trick for this, but personally I would try solving for the direct formula (for inspiration, check wikipedia)
 
Here is what my professor wrote (I don't completely understand what he did):
An= c1\alphan + c2\betan
c1,c2= 3 \pm \sqrt{}15
Bn= c3\deltan + c4\varpin
c3,c4= (5 \pm \sqrt{}61)/2

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

An > Bn for all n
since \alpha > \delta > \varpi

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?
 

Similar threads

  • · Replies 1 ·
Replies
1
Views
1K
Replies
3
Views
3K
  • · Replies 12 ·
Replies
12
Views
2K
Replies
3
Views
3K
  • · Replies 8 ·
Replies
8
Views
3K
Replies
3
Views
10K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 7 ·
Replies
7
Views
2K
Replies
6
Views
5K
Replies
235
Views
15K