# (Long) Fibonacci Sequence Question

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}$$

-
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. –  André Nicolas Mar 29 '12 at 10:16

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}$.

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$$

-