# Recurrence $a_{n+1} = xa_n$ using generating function

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?

• 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. – GEdgar Aug 4 '13 at 18:43
• Yes, but Wilf uses x in his example. – Val Aug 4 '13 at 18:45
• 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? – GEdgar Aug 4 '13 at 18:52
• What does Wilf want writing this example in generating functionology, math.upenn.edu/~wilf/DownldGF.html, at page 19? – Val Aug 4 '13 at 18:54
• 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$. – Zander Aug 4 '13 at 19:35

## 1 Answer

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$