0
$\begingroup$

Let's define the sequence $a_n$, $n \geq 0$ by making $a_0 = 0$ and $a_{n+1} = 2a_n + n$ for $n \geq 0$. Show that if $F(x) = \sum_{n=0}^{\infty} a_nx^n$ is the generating function of the sequence, then $$F(x) = \frac{x^2}{(1-x)^2(1-2x)}$$

$\endgroup$
  • $\begingroup$ Could you tell what you already tried ? $\endgroup$ – Claude Leibovici Apr 6 '14 at 13:30
  • $\begingroup$ $$\frac{A}{(1-x)^2}+\frac{B}{1-x}+\frac{C}{1-2x} = \frac{x²}{(1-x)^2(1-2x)}$$ $\endgroup$ – Franklin Apr 6 '14 at 13:54
  • $\begingroup$ So, what are $A,B,C$ ? $\endgroup$ – Claude Leibovici Apr 6 '14 at 14:08
3
$\begingroup$

$F(x) = \displaystyle{\sum_{n=1}^\infty a_n x^n} = \displaystyle{\sum_{n=1}^\infty (2a_n + n) x^n} = 2\displaystyle{\sum_{n=1}^\infty a_n x^n} + \displaystyle{\sum_{n=1}^\infty n x^n} = 2xF(x) + \displaystyle{\sum_{n=1}^\infty n x^n}$

Now, we know that $\dfrac{1}{1-x} = \displaystyle{\sum_{n=0}^\infty x^n}$, for $|x|<1$. Deriving in both sides, $\dfrac{1}{(1-x)^2} = \displaystyle{\sum_{n=1}^\infty n x^{n-1}}$. Multiplying by $x$ in both sides, $\dfrac{x}{(1-x)^2} = \displaystyle{\sum_{n=1}^\infty n x^n}$.

Therefore:

$$F(x) = 2xF(x) + \dfrac{x}{(1-x)^2}$$

$$F(x) = \frac{x^2}{(1-x)^2(1-2x)}$$

$\endgroup$
  • $\begingroup$ How did you go from this $$F(x) = 2F(x) + \frac{x}{(1-x)^2}$$ to this $$F(x)= \frac{x²}{(1-x)²(1-2x)}$$ $\endgroup$ – Franklin Apr 6 '14 at 15:36
  • $\begingroup$ Just isolate $F(x)$ $\endgroup$ – Imanol Pérez Arribas Apr 6 '14 at 19:15
  • 2
    $\begingroup$ I've edited my answer. I've forgotten an $x$. ($F(x) = 2F(x) + \frac{x}{(1-x)^2}$) $\endgroup$ – Imanol Pérez Arribas Apr 6 '14 at 20:10
0
$\begingroup$

Multiply your recurrence by $x^n$, sum over $n \ge 0$, and recognize: \begin{align} \sum_{n \ge 0} a_{n + 1} x^n &= \frac{F(x) - a_0}{x} \\ \sum_{n \ge 0} n x^n &= x \frac{\mathrm{d}}{\mathrm{d} x} \frac{1}{1 - x} \\ &= \frac{x}{(1 - x)^2} \end{align} to get: $$ \frac{F(x)}{x} = 2 F(x) + \frac{x}{(1 - x)^2} $$ This results in: $$ F(x) = \frac{x^2}{1 - 4 x + 5 x^2 - 2 x^3} = \frac{x^2}{(1 - x)^2 (1 - 2 x)} = \frac{1}{1 - 2x} - \frac{1}{(1 - x)^2} $$ Expanding by the generalized binomial theorem gives: $$ a_n = 2^n - n - 1 $$

$\endgroup$

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.