Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.
Trending News
Discrete Math II: Generating Function?
Hello, currently i'm taking Discrete Math II (MTH481) for my CS major. I'm stuck on generating functions, and the book doesn't give us a good example on these problems. Can you walk me through this question from my homework?
Use Generating functions to solve the recurrence relation, a_k = 7_a(k-1) with the initial condition a_0 = 5.
Underscore = Subscript.
Thanks in advanced!
Awesome explination kb! Just a couple more questions on the solving method...
-What allows x^k to become x^(k-1) in your 3rd step?
-How did you get from
G(x) - 5 = 7x * G(x)
to
G(x) = 5/(1 - 7x) ...?
Thanks for clearing it up :-D
NVM, i figured it out :)
1 Answer
- kbLv 71 decade agoFavorite Answer
Let G(x) = Σ(k=0 to ∞) a_k * x^k.
Given a_k = 7 * a_(k-1), multiply both sides by x^k and sum over k = 1, 2, 3, ...:
a_k * x^k = 7 * a_(k-1) * x^k
==> a_k * x^k = 7x * a_(k-1) * x^(k-1)
==> Σ(k=1 to ∞) a_k * x^k = Σ(k=1 to ∞) 7x * a_(k-1) * x^(k-1)
==> G(x) - a_0 = 7x * G(x)
==> G(x) - 5 = 7x * G(x)
Solving for G(x) yields
G(x) = 5/(1 - 7x)
.......= 5 * Σ(k=0 to ∞) (7x)^k, by using the geometric series
.......= Σ(k=0 to ∞) (5 * 7^k) x^k
Since G(x) = Σ(k=0 to ∞) a_k * x^k, we conclude that a_k = 5 * 7^k.
I hope this helps!
