5
$\begingroup$

I am working on a rather long question. I am going to write out the question, and what I've come up with so far. I'm not sure if the question has too many parts to receive answers but I will appreciate any help at all.

The question is

The Fibonacci sequence $(a_{n})_{n=0}^\infty$ is defined by $a_{0}=1$, $a_{1}=1$ and $a_{n+1}:=a_{n}+a_{n-1}$ for all $n\geq 1$.

(a) Show that $\frac {a_{n+1}}{a_{n}}\leq 2$ for $n\geq 0$

(b) Let $f(x):=\sum_{n=0}^{\infty}a_{n}x^{n}$. Show that $f(x)$ converges if $|x|<\frac{1}{2}.$

(c) If $|x|<\frac {1}{2}$ then prove that $f(x)=\frac{1}{1-x-x^{2}}$.

(d) Use the partial fraction decomposition for $\frac {1}{1-x-x^{2}}$ and the geometric series to obtain another power series expression for $f$.

(e) By comparing coefficients, show that $a_{n}=\frac {1}{\sqrt{5}}\left ( \left ( \frac{1+\sqrt{5}}{2} \right )^{n+1}- \left ( \frac{1-\sqrt{5}}{2} \right )^{n+1} \right )$

I will begin with what I've been able to accomplish and my intuition so far, in order of the parts of the question.


(a) I've begun by rearranging as follows:

$\frac {a_{n+1}}{a_{n}}=\frac {a_{n}+a_{n-1}}{a_{n}}\leq 2$ $1+\frac {a_{n-1}}{a_{n}}\leq 2$ $\frac {a_{n-1}}{a_{n}}\leq 1$

So I've got to show that $a_{n-1}\leq a_{n}$ for $n\geq 0$. Intuitively this makes sense to me. The Fibonnaci sequence is constantly increasing (accept for the first two terms). A term will always be smaller or equal to the term that comes after it. I've tried to prove this using induction but I have been unsuccessful. Maybe what I have is sufficient?


(b) This one clearly follows from part (a). I've done the following using the ratio test to find the radius of convergence.

Let $b_{n}=a_{n}x^{n}$ and $b_{n+1}=a_{n+1}x^{n+1}$. So,

$\left | \frac {b_{n+1}}{b_{n}} \right |=\left | \frac {a_{n+1}x^{n+1}}{a_{n}x^{n}} \right | = \frac {a_{n+1}}{a_{n}} \cdot |x|$

Taking the limit

$\lim_{n \to \infty} \frac {a_{n+1}}{a_{n}} \cdot |x|=(\lim_{n \to \infty} \frac {a_{n+1}}{a_{n}}) \cdot |x|=L$

The limit $n \to \infty$ of $\frac {a_{n+1}}{a_{n}}$ can not be greater than 2. I also know that $L$ cannot be greater than 1 in order for there to be convergence. I've tried this

Let $1< \epsilon \leq 2$.

$(\lim_{n \to \infty} \frac {a_{n+1}}{a_{n}}) \cdot |x|=\epsilon |x|<1$

Then $|x|<1/\epsilon$. But this doesn't work. If, for example, as allowed by the conditions I stated, $\epsilon=1.2$, then $|x|>1/2$.


(c) I've done the following based on the Wikipedia entry for Fibonacci sequences.

$f(x)=\sum_{n=0}^{\infty}a_{n}x^{n}$

$=a_{0}+a_{1}x+\sum_{n=2}^{\infty}(a_{n-1}+a_{n-2})x^{n}$

$=1+x+\sum_{n=2}^{\infty}a_{n-1}x^{n}+\sum_{n=2}^{\infty}a_{n-2}x^{n}$

$=1+x+x \cdot \sum_{n=0}^{\infty}a_{n}x^{n}+x^{2} \cdot \sum_{n=0}^{\infty}a_{n}x^{n}$

So,

$f(x)=1+x+xf(x)+x^2f(x)=\frac {1+x}{1-x-x^{2}}$

Obviously I've gone wrong somewhere. Taking a different route I recognized that because $|x|<1/2<1$, I can rewrite $f$ as

$f(x)=\frac {1}{1-x} \cdot \sum_{n=0}^{\infty}a_{n}$

This has not proved useful as of yet.


(d) I've found the partial fraction decomposition using Wolfram Alpha to be

$\frac {1}{1-x-x^2}=\frac {2}{(5+\sqrt{5})+(\sqrt{5}\cdot 2x)}+\frac {2}{(5-\sqrt{5})-(\sqrt{5}\cdot 2x)}$

$= \frac {2}{5+\sqrt{5}} \cdot \frac {1}{x \frac{2}{\sqrt{5}+1}+1}+\frac {2}{5-\sqrt{5}} \cdot \frac {1}{x \frac{2}{\sqrt{5}-1}+1}$

$=\frac {2}{5+\sqrt{5}} \cdot \sum_{n=0}^{\infty}(\frac{2x}{\sqrt{5}+1})^{n}+\frac {2}{5-\sqrt{5}} \cdot \sum_{n=0}^{\infty}(\frac{2x}{\sqrt{5}-1})^{n}$

  • 0
    Giving partial summary of what I wrote, there is an answer already. I don't think you need to prove the sequence is non-decreasing. Just say $\frac{a_{n+1}}{a_n}=\frac{a_n+a_{n-1}}{a_n}=1+\frac{a_{n-1}}{a_n}\le 2$. Can't quite use ratio test like you did, though can if you use $\limsup$ version. Or else note that $a_n \le 2^n$, so there is absolute convergence when |x|<1/2 by comparison with geometric series. Note that Wikipedia, uses $F_0=0$, $F_1=1$, so your generating function will not be identical to the Wikipedia one, even after you correct the summation symbol error.2012-03-29

1 Answers 1

2

For part (a) you need to use the strong law of induction -- or at least something a little stronger than the usual version. Let $P(n)$ be the statement that $a_n \geq a_{n-1}$. Then we will show that $P(n)$ is true for $n=1,2$ and we will show that if $P(n)$ is true for $n=k$ and $n=k-1$ then it is true for $n=k+1$. The strengthening here is that we need $P(n)$ to be true for the two preceding terms in the sequence.

The $n=1,2$ cases are obviously trivial. For the inductive step we have $ a_k \geq a_{k-1}, \,\,\,\, a_{k-1}\geq a_{k-2}$ from which it follows that $ a_k \geq a_{k-2}$ $ a_k +a_{k-1}\geq a_{k-1} +a_{k-2}$ $ a_{k+1}\geq a_{k}$ and so $P(n)$ is true for all $n\in\mathbb{N}$.


Your part (b) is good.


For part (c), you've made an error with your summations. We have $ \sum_{n=2}^\infty a_{n-1}x^n = \sum_{n=1}^\infty a_{n}x^{n+1}= x\sum_{n=1}^\infty a_{n}x^{n} $ As we can see, we're missing the first term in the sum. Thus $ \sum_{n=2}^\infty a_{n-1}x^n =x\left[ \sum_{n=1}^\infty a_{n}x^{n} + a_0 - a_0\right] = x(f(x)-a_0) $ The equation then becomes $ f(x) = 1 + x + x(f(x) - 1) + x^2 f(x) $ which gives the correct answer. You have to be really careful when changing the index of a summation -- my advice would be to write out the first few terms of the sum you start with and the one you end as a check that they're the same.

Your remark that you can write $f$ as $ f(x) = \frac{1}{1-x} \sum_{n=0}^\infty a_n = \left( \sum_{n=0}^\infty x^n \right) \left( \sum_{n=0}^\infty a_n \right) $ is wrong. You're multiplying those two series incorrectly.


Part (d): now apply the geometric formula. I'll do an easier one. Suppose you have $ f(x) = \frac{2}{3+5x} $ We need this in the form A/(1-Bx) to use the formula. We have,

$ f(x) = \frac{2}{3+5x} = \frac{1}{3}\frac{2}{1+5x/3} = \frac{2}{3}\frac{1}{1-(-5x/3)} $ Thus $ f(x) = \frac{2}{3} \sum_{n=0}^\infty \left( \frac{-5x}{3} \right)^n = \sum_{n=0}^\infty \frac{2}{3} \left( \frac{-5}{3} \right)^n x^n $

Part (e) then follows -- in this case we would have $ a_n = \frac{2}{3} \left( \frac{-5}{3} \right)^n $