I read the generating functionology, where author handles $$b_k(x) = {x \over 1-kx} b_{k-1}(x) = {x ^k \over (1-x)(1-2)(1-3x) \cdots (1-kx)}$$ since $b_0(x) = 1.$ I see that if denominator $(1-kx)$ would be 1 in the recurrence, I would have simpler recurrence, $b_k = x b_{k-1} = x^k b_0$. I understand the logic. You unroll $b_{k-1}$ in terms of $b_{k-2}$ and so on: $b_k = x b_{k-1} = x (x b_{k-2}) = x (x(xb_{k-3})) = x^k b_{k-k}$. But I fail to expand $b_k = x b_{k-1}$ into $x^k$ using the generating functions.

Say you have $a_{n+1} = 3 a_n$. You may spot that $a_n = 3^n a_0$ using the logic above or work out $$a(x) = \sum_{n=0} {a_n x^n}$$ so that $$\sum_{n=0} a_{n+1} x^n = {\sum_{n=0} {a_{n+1} x^{n+1}} ± a_0 \over x} = {(a(x) - a_0) \over x}.$$ Now, equation $a_{n+1} = 3 a_n$ is rewritten as $${a(x) - a_0 \over x} = 3 a(x)$$ and $$a(x) = \frac{a_0}{1-3x} = \sum_{n=0} {(a_0 3^n) x^n} = \sum_{n=0} {a_n x^n} $$ so that $a_n = a_0 3^n$ in the series. Now, I have $x$ instead of 3 in $a_{n+1} = x a_n$. I may write down the solution $a_n = a_0 3^n$ right away. But, if I try to solve it the same way, I get the $a(x) = a_0 / (1-x^2)$ instead of $a(x) = a_0 / (1-3x)$ and $$a(x) = {a_0 \over 1-x^2} = {a_0 \over 1-x} \cdot {a_0 \over 1+x} = a_0\sum_{n=0} {1^n x^n} + a_0\sum_{n=0} {(-1)^nx^n}$$ so that $a_{n+1} = x a_n$ has solution $a_n = a_0 (1+(-1)^n)$ instead of $a_n = a_0 x^n.$ What is the mistake? Why does Wilf not fall into it?

Isn't it too localized? Can I reword the problem so that it is interesting for general audience?

  • $\begingroup$ Are you trying to solve $a_{n+1}(x) = xa_n(x)$ for a sequence of functions of $x$? If so, and if I were required to use "generating functions" to do it, I would use some other variable as the variable for the g.f. $\endgroup$ – GEdgar Aug 4 '13 at 18:43
  • $\begingroup$ Yes, but Wilf uses x in his example. $\endgroup$ – Val Aug 4 '13 at 18:45
  • $\begingroup$ You write $a(x) = \sum_{n=0} {a_n x^n}$, which makes no sense to me unless $a_n$ is not a function of $x$; but you also write $a_{n+1} = xa_n$ which makes no sense to me unless $a_n$ is a funtion of $x$. What do you want? $\endgroup$ – GEdgar Aug 4 '13 at 18:52
  • $\begingroup$ What does Wilf want writing this example in generating functionology, math.upenn.edu/~wilf/DownldGF.html, at page 19? $\endgroup$ – Val Aug 4 '13 at 18:54
  • $\begingroup$ Wilf has a recurrence in two variables $k,n$ which he's solving with a sequence of generating functions $B_k(x)=\sum b_{k,n} x^n$. $\endgroup$ – Zander Aug 4 '13 at 19:35

Let's say we want $a_{n+1}(x) = x a_n(x)$. Then $$ a(x) = \frac{a_0(x)}{1-x^2} $$ is correct.

But if $$ \sum_{n=0}^\infty a_n(x) x^n = \sum_{n=0}^\infty u_n x^n, $$ for all $x$, it does not follow that $a_n(x)=u_n$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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