If 1 − x − x 2 x can be expressed in the form n = 1 ∑ ∞ a n x n for a certain subset of reals such that a i ∈ R and ∀ i ∈ N , what is the value of n → ∞ lim a n a n + 1 ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
You can use Binet's formula for that!
We can show that 1 − x − x 2 x is the generating function of the Fibonacci number by long division method. It rather difficult to show here.
1 − x − x 2 x = 1 − x − x 2 x ( 1 − x − x 2 ) + x 2 + x 3 = x + 1 − x − x 2 x 2 + x 3
= x + 1 − x − x 2 x 2 ( 1 − x − x 2 ) + 2 x 3 + x 4 = x + x 2 + 1 − x − x 2 2 x 3 + x 4
= x + x 2 + 1 − x − x 2 2 x 3 ( 1 − x − x 2 ) + 3 x 4 + 2 x 5 = x + x 2 + 2 x 3 + 1 − x − x 2 3 x 4 + 2 x 5
= x + x 2 + 2 x 3 + 1 − x − x 2 3 x 4 ( 1 − x − x 2 ) + 5 x 5 + 3 x 6
= x + x 2 + 2 x 3 + 3 x 4 1 − x − x 2 5 x 5 + 3 x 6
= x + x 2 + 2 x 3 + 3 x 4 + 1 − x − x 2 5 x 5 ( 1 − x − x 2 ) + 8 x 6 + 5 x 7
= x + x 2 + 2 x 3 + 3 x 4 + 5 x 5 + 1 − x − x 2 8 x 6 + 5 x 7
= x + x 2 + 2 x 3 + 3 x 4 + 5 x 5 + 8 x 6 + 1 3 x 7 + . . .
About lim n → ∞ a n a n + 1 , I don't know what φ is, but my answer is as follows:
lim n → ∞ a n a n + 1 = lim n → ∞ a n + 1 a n + 2
lim n → ∞ a n a n + 1 − a n + 1 a n + 2 = 0
lim n → ∞ a n a n + 1 a n + 1 2 − a n a n + 2 = 0
⇒ lim n → ∞ a n + 1 2 − a n a n + 2 = 0
Continue...
Note that a n + 1 = a n + a n − 1 , so that:
lim n → ∞ a n + 1 2 − a n a n + 2 = 0
⇒ lim n → ∞ a n + 1 2 − a n ( a n + 1 + a n ) = 0
lim n → ∞ ( a n a n + 1 ) 2 − a n a n + 1 − 1 = 0
lim n → ∞ a n a n + 1 = 2 1 + 1 + 4 = 2 1 + 5 = 1 . 6 1 8
The power-series expansion of 1 − x − x 2 x is valid for all (and only) ∣ x ∣ < α , where α is the positive zero of the denominator, i.e. 1 − α − α 2 = 0 , i.e., α = ϕ , the golden ratio.
Now from the ratio-test, we know it is sufficient that lim n → ∞ ∣ a n ∣ ∣ a n + 1 ∣ ∣ y ∣ < 1 for the series to converge at x = y . Since α is the radius of convergence, at x = α the above ratio should be one. Hence lim n → ∞ ∣ a n ∣ ∣ a n + 1 ∣ = ϕ 1 . Also, from the series expansion it is evident that all the coefficients are non-negative. Thus lim n → ∞ a n a n + 1 = ϕ 1 .
Doing a long division, we quickly discover that, whenever the right hand side converges (i.e. when |x|<1): 1 − x − x 2 x = x + x 2 + 2 x 3 + 3 x 4 + 5 x 5 + . . . + F n x n + . . . Where F n is the nth fibonacci number (in addition, we define F 0 = 0 ). This implies that the nth-order derivative of this expression has one constant term: n ! F n . So the nth order derivatife evaluated at 0 : f ( n ) ( 0 ) = n ! F n
The maclaurin series (or Taylor expansion in 0) of f is
f ( x ) = n = 0 ∑ ∞ n ! f ( n ) ( 0 ) x n = n = 0 ∑ ∞ F n x n
and hence the requested expression equals φ = 2 5 + 1 = 1 . 6 1 8 0 3 . . .
It is well-known that 1 − x − x 2 x is the generating function of the fibonacci numbers. Thus, n → ∞ lim a n a n + 1 = φ = 1 . 6 1 8
If we need to prove that 1 − x − x 2 x is the generating function of the fibonacci numbers, then have fun guys.
Problem Loading...
Note Loading...
Set Loading...
Write out 1 − x − x 2 x as a power series and manipulate
1 − x − x 2 x x x x x = n = 1 ∑ ∞ a n x n = ( 1 − x − x 2 ) n = 1 ∑ ∞ a n x n = n = 1 ∑ ∞ a n x n − n = 1 ∑ ∞ a n x n + 1 − n = 1 ∑ ∞ a n x n + 2 = a 1 x + a 2 x 2 − a 1 x 2 + n = 3 ∑ ∞ ( a n − a n − 1 − a n − 2 ) x n = a 1 x + ( a 2 − a 1 ) x 2 + n = 3 ∑ ∞ ( a n − a n − 1 − a n − 2 ) x n
Now relate the coefficients. this gives a 1 = 1 and a 2 − a 1 = 0 ⟹ a 2 = a 1 = 1 . Then the other coefficients have to equal zero as well meaning we have the recurrence relation a n − a n − 1 − a n − 2 = 0 ⟹ a n = a n − 1 + a n − 2 .
Now because a 1 = a 2 = 1 and we have an addition relation it means that a n = F n where F n are the Fibonacci numbers.
Therefore n → ∞ lim a n a n + 1 = n → ∞ lim F n F n + 1 = ϕ ≈ 1 . 6 1 8 The last one is a well known limit.
Edit: To expand on deriving the limit
L L L L L = n → ∞ lim F n F n + 1 = n → ∞ lim F n F n + F n − 1 = 1 + n → ∞ lim F n F n − 1 = 1 + n → ∞ lim F n + 1 F n 1 = 1 + L 1
The last equation can be solved easily. It is the definition of the golden ratio and can be turned into a quadratic to yield it also. But be careful about introducing a new solution when turning it into a quadratic.