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$
3
  • $\begingroup$ Could you tell what you already tried ? $\endgroup$ Apr 6, 2014 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, 2014 at 13:54
  • $\begingroup$ So, what are $A,B,C$ ? $\endgroup$ Apr 6, 2014 at 14:08

2 Answers 2

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$
3
  • $\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, 2014 at 15:36
  • $\begingroup$ Just isolate $F(x)$ $\endgroup$ Apr 6, 2014 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$ Apr 6, 2014 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .