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