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) =

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.

in progress 0
Khang Minh 5 months 2021-08-29T21:04:31+00:00 1 Answers 0 views 0

Answers ( )

    0
    2021-08-29T21:06:25+00:00

    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)

Leave an answer

Browse

Giải phương trình 1 ẩn: x + 2 - 2(x + 1) = -x . Hỏi x = ? ( )