Question

Recall that the Fibonacci Sequence is defined by the recurrence relation, a0 = a1 = 1 and for n ≥ 2, an = an−1 + an−2 . a. Show that f(x) = 1 1−x−x 2 is the generating function of the Fibonacci Sequence. b. Find ???? and β such that 1 − x − x 2 = (1 − ????x)(1 − βx). c. Find A and B in terms of ???? and β, such that 1 1−x−x 2 = A 1−????x + B 1−βx. d. Use the results of the previous parts to obtain a formula for an.

Answer 1

Answer:

Step-by-step explanation:

From the given information:

$a_n = a_{n-1} + a_{n-2}; \ \ \ n \ge 2 \\ \\ a_o = 1 \\ \\ a_1 =1 \ \ \ \ \ since \ \ a_o = a_1 = 1$

A)

$a_n - a_{n-1} - a_{n-2} = 0 \\ \\ \implies \sum \limits ^{\infty}_{n=2}(a_n -a_{n-1}-a_{n-2} ) x^n = 0 \\ \\ \implies \sum \limits ^{\infty}_{n=2} a_nx^n - \sum \limits ^{\infty}_{n=2} a_{n-1}x^n - \sum \limits ^{\infty}_{n=2}a_{n-2} x^n = 0 \\ \\ \implies (a(x) -a_o-a_1x) - (x(a(x) -a_o)) -x^2a(x) = 0 \\ \\ \implies a(x) (1 -x-x^2) -a_o-a_1x+a_ox = 0 \\ \\ \implies a(x)(1-x-x^2)-1-x+x=0 \\ \\ \implies a(x) (1-x-x^2) = 1$

$\mathbf{Generating \ Function: a(x) = \dfrac{1}{1-x-x^2}=f(x)}$

B)

$If \ \ 1 -x-x^2 = (1 - \alpha x) ( 1- \beta x) \\ \\ \implies 1 -x - ^2 = 1 + \alpha \beta x^2 - ( \alpha + \beta )x \\ \\ \text{It implies that:} \\ \\ \alpha \beta = -1 \\ \\ \alpha + \beta = 1 \\ \\ \implies \alpha = ( 1-\beta) \\ \\ ( 1- \beta) \beta = -1 \\ \\ \implies \beta - \beta^2 = -1 \implies \beta - \beta^2 -1 = 0\\ \\ \beta = \dfrac{-(-1) \pm \sqrt{(-1)^2 -4(1)(-1)}}{2(1)}$

$\beta = \dfrac{1\pm \sqrt{5}}{2} \\ \\ \beta = \dfrac{1 + \sqrt{5}}{2} \ \ and \ \ \alpha = \dfrac{1 - \sqrt{5}}{2}$

C)

$\dfrac{1}{1-x-x^2}= \dfrac{A}{1-\alpha x}+ \dfrac{\beta}{1-\beta x} \\ \\ = \dfrac{A(1-\beta x) + B(1-\alpha x)}{(1-\alpha x) (1 - \beta x)} \\ \\ = \dfrac{(A+B)-(A\beta+B\alpha)x}{(1-\alpha x) (1-\beta x)}$

$\text{It means:} \\ \\ A+B=1 \\ \\ B = (1-A) \\ \\ A\beta+ B \alpha =0 \\ \\ A\beta ( 1 -A) \alpha = 0 \\ \\ A( \beta - \alpha ) = -\alpha \\ \\ A = \dfrac{\alpha}{\alpha - \beta } \\ \\ \\ \\ B = 1 - \dfrac{\alpha }{\alpha - \beta} \implies \dfrac{\alpha - \beta - \alpha }{\alpha - \beta } \\ \\ =\dfrac{-\beta }{\alpha - \beta} \\ \\ \mathbf{B = \dfrac{\beta }{\beta - \alpha }}$

D)

$\text{The formula for} a_n: \\ \\ a(x) = \dfrac{\alpha }{\alpha - \beta }\sum \limits ^{\infty}_{n=0} \alpha ^n x^n - \dfrac{\beta}{\beta - \alpha }\sum \limits ^{\infty}_{n=0} \beta x^n \\ \\ \implies \sum \limits ^{\infty}_{n =0} \dfrac{\alpha ^{n+1}- \beta ^{n+1}}{\alpha - \beta}x^n \\ \\ a_n = \dfrac{\alpha ^{n+1}- \beta ^{n+1}}{\alpha - \beta } \\ \\ \\ a_n = \dfrac{1}{\sqrt{5}} \Big (\Big( \dfrac{\sqrt{5}+1}{2}\Big)^{n+1}- \Big ( \dfrac{1-\sqrt{5}}{2}\Big) ^{n+1}\Big)$