Using generation functions solve the following difference equation

1,803

Solution 1

Thanks for the hint was able to solve it. This was my solution.

$$ a_{n+1} - 3a_{n+2} + 2a_n = 7n ; n\geq0; a_0 = -1; a_1 = 3. $$

$$ (\frac{a{(z)} - a_{0} + za_1}{z^2}) - 3(\frac{a{(z)} - a_{0}}{z^2}) + 2a(z) = \frac{7z}{(1 - z)^2}; a_0 = -1; a_1 = 3. $$

Substitute values in:

$$ (\frac{a{(z)} + 1 - 3z}{z^2}) - 3(\frac{a{(z)} + 1}{z^2}) + 2a(z) = \frac{7z}{(1 - z)^2}; a_0 = -1; a_1 = 3. $$

Expand and multiply through by $z^2$

$$ a(z) + 1 -3z - 3a(z)z -3z + 2a(z)z^2 = \frac{7z^3}{(1 - z)^2} $$

$$ a(z)[1 -3z + 2z^2] = \frac{7z^3}{(1 - z)^2} + 6z - 1 $$

$$ a(z) = \frac{13z^3 - 13z^2 + 8z -1}{(z-1)^2(2z-1)}$$

By Partial Fraction decomposition:

$$ a(z) = \frac{-11}{(2z-1)} + \frac{12}{(z-1)} + \frac{7}{(z-1)^2} + \frac{7}{(z-1)^3}$$

By Extracting coefficients we get: $$ a(z) = \frac{-7[n(n+1)]}{2} + 11 * 2^n - 12$$

Solution 2

Define the generating function $A(z) = \sum_{n \ge 0} a_n z^n$, multiply your recurrence by $z^n$ and sum over $n \ge 0$, Recognize, e.g.: \begin{align} \sum_{n \ge 0} a_{n + 2} z^n &= \frac{A(z) - a_0 - a_1 z}{z^2} \\ \sum_{n \ge 0} z^n &= \frac{1}{1 - z} \\ \sum_{n \ge 0} n z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \end{align} Solve the result for $A(z)$, write as partial fractions (a computer algebra system helps), and read off the coefficients by using geometric series or: $$ (1 + u)^{-m} = \sum_{k \ge 0} \binom{-m}{k} u^k = \sum_{k \ge 0} \binom{k + m - 1}{m - 1} (-1)^k u^k $$

Share:
1,803

Related videos on Youtube

Daniel
Author by

Daniel

Basketball & Programming

Updated on August 20, 2022

Comments

  • Daniel
    Daniel about 1 year

    Using generation functions solve the following difference equation

    $$ a_{n+1} - 3a_{n+2} + 2a_n = 7n ; n\geq0; a_0 = -1; a_1 = 3. $$

    • 5xum
      5xum over 9 years
      What have you done so far and where are you stuck?
    • ShreevatsaR
      ShreevatsaR over 9 years
      The same question was posted an hour ago by the same user, who's since deleted it for unclear reasons.
    • Claude Leibovici
      Claude Leibovici over 9 years
      Why did you delete the previous post ?
    • Daniel
      Daniel over 9 years
      @ClaudeLeibovici It was a mistake I deleted it and didn't know how to get it back. I'm new to this
    • Mhenni Benghorbal
      Mhenni Benghorbal over 9 years
    • Did
      Did over 9 years
      "It was a mistake" Hmmm... and you also chose to disregard the advice given to you there that "You can post your initial steps, and also what final answer you got" (advice repeated here by another user, and similarly disregarded).
  • Anant
    Anant over 9 years
    Typo: $(1+u)^\color{red}{m}$
  • vonbrand
    vonbrand over 9 years
    @Anant, thank you. Fixed.
  • Daniel
    Daniel over 9 years
    Thanks for the hint was able to solve it. This was my solution. @vonbrand
  • vonbrand
    vonbrand over 9 years
    That's how it is done. Did you check the solution?I believe you left out the term with the square.