Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.