Find $F_{n}$ in : $F_{n} +2F_{n-1} + ... + (n+1)\cdot F_{0} = 3^{n}$ I'm stuck with the question for a while : Find in $$F_{n} +2F_{n-1} + ... + (n+1)\cdot F_{0} = 3^{n}$$
the element $F_{n}$ .
Placing $n-1$ instead on $n$ results in : 
$$F_{n-1} +2F_{n-2} + ... + (n-1+1)\cdot F_{0} = 3^{n-1}$$
$$ F_{n-1} +2F_{n-2} + ... + n\cdot F_{0} = 3^{n-1} $$
subtracting both : 
$$F_{n} +2F_{n-1} + ... + (n+1)\cdot F_{0} -(F_{n-1} +2F_{n-2} + ... + n\cdot F_{0} )
=3^{n} - 3^{n-1}
$$
But that doesn't help much . Any ideas ? 
Thanks 
 A: The condition
$$F_{n} +2F_{n-1} + ... + (n+1)\cdot F_{0} = 3^{n}$$
is equivalent to the equality of coefficients of $z^n$ in below expression:
$$( F_0 + F_1 z + F_2 z^2 + \cdots )(1 + 2z + 3z^2 + \cdots ) = 1 + 3z + 3^2 z^2 + \cdots$$
Notice $\frac{1}{(1-z)^2} = 1 + 2z + 3z + \cdots$ and $\frac{1}{1-3z} = 1 + 3z + 3^2 z^2 + \cdots$, we have:
$$\frac{\sum_{k=0}^{\infty} F_k z^k}{(1-z)^2} = \frac{1}{1-3z} \quad\implies\quad\sum_{k=0}^{\infty} F_k z^k  = \frac{(1-z)^2}{1-3z} = \frac{1 - 2z + z^2}{1-3z}$$
By comparing the coefficients of $z^n$, we get:
$$\begin{align}
F_0 &= 1\\
F_1 &= 1\cdot 3^1 - 2 \cdot 1 = 1\\
&\;\vdots\\
F_n &= 1\cdot 3^n - 2 \cdot 3^{n-1} + 1 \cdot 3^{n-2} = 4\cdot 3^{n-2},\quad\text{ for }n \ge 2
\end{align}$$
A: HINT: If you do the algebra, you’ll find that your last equation reduces to
$$F_n+F_{n-1}+F_{n-2}+\ldots+F_0=2\cdot 3^{n-1}\;.$$
Substituting $n-1$ for $n$ yields the equation
$$F_{n-1}+F_{n-2}+\ldots+F_0=2\cdot3^{n-2}\;.$$
Now what’s $F_n$?
A: Generating functions are your friends.
With experience, you will recognize that sum
as a convolution.
All that follows is standard generating function manipulation.
See the book "generatingfunctionology"
available free online
at
http://www.math.upenn.edu/~wilf/DownldGF.html.
Note: This may seem unnecessarily complicated,
but sometimes generating functions
are the most direct way to get results.
Let
$A(x) = \sum_{n=0}^{\infty} F_n x^n
$,
$B(x) = \sum_{n=0}^{\infty} (n+1) x^n
$,
and
$C(x) = A(x) B(x)
$.
$\begin{align}
C(x) 
&= A(x) B(x)\\
&= \left(\sum_{n=0}^{\infty} F_n x^n\right) \left( \sum_{n=0}^{\infty} (n+1) x^n\right)\\
&= \sum_{i=0}^{\infty} \sum_{j-0}^{\infty} (j+1)F_i x^{i+j}\\
&= \sum_{n=0}^{\infty}\sum_{i=0}^{n}  (n-i+1)F_i x^n
\quad\text{ Setting }i+j=n\text{, so } j=n-i\\
&= \sum_{n=0}^{\infty} x^n\sum_{i=0}^{n}  (n-i+1)F_i\\
\end{align}
$
By assumption,
$\sum_{i=0}^{n}  (n-i+1)F_i = 3^n$.
So
$C(x) = A(x)B(x)
=\sum_{n=0}^{\infty}3^n x^n
=\sum_{n=0}^{\infty} (3x)^n
= \dfrac{1}{1-3x}
$.
If we can find $B(x)$,
we can get $A(x) = C(x)/B(x)$.
$\begin{align}
B(x) 
&= \sum_{n=0}^{\infty} (n+1) x^n\\
&= \sum_{n=0}^{\infty} (x^{n+1})'\\
&= \left(\sum_{n=0}^{\infty} x^{n+1}\right)'\\
&= \left(\dfrac{x}{1-x}\right)'\\
&= \dfrac{(1-x)+x}{(1-x)^2}\\
&= \dfrac{1}{(1-x)^2}\\
\end{align}
$
so
$\begin{align}
A(x) 
&= \dfrac{1}{1-3x}\big/\dfrac{1}{(1-x)^2}\\
&= \dfrac{(1-x)^2}{1-3x}\\
&= (1-2x+x^2)\sum_{n=0}^{\infty} 3^n x^n\\
&= \sum_{n=0}^{\infty} 3^nx^n
-\sum_{n=0}^{\infty} 2\ 3^nx^{n+1}
+\sum_{n=0}^{\infty} 3^nx^{n+2}\\
&= \sum_{n=0}^{\infty} 3^nx^n
-\sum_{n=1}^{\infty} 2\ 3^{n-1}x^{n}
+\sum_{n=2}^{\infty} 3^{n-2}x^{n}\\
&= 1+3x+\sum_{n=2}^{\infty} 3^nx^n
-2x-\sum_{n=2}^{\infty} 2\ 3^{n-1}x^{n}
+\sum_{n=2}^{\infty} 3^{n-2}x^{n}\\
&= 1+x +\sum_{n=2}^{\infty} x^n(3^n-2\ 3^{n-1}+3^{n-2})
\quad(*)\text{ We can stop here to get } F_n\\
&= 1+x +\sum_{n=2}^{\infty} x^n 3^n(1-2/3+1/9))
\quad\text{ Continuing on anyway to get } A(x)\\
&= 1+x +(4/9)\sum_{n=2}^{\infty} x^n 3^n\\
&= 1+x +(4/9)\dfrac{9x^2}{1-3x}\\
&= \dfrac{(1+x)(1-3x)+4x^2}{1-3x}\\
&= \dfrac{1-2x+x^2}{1-3x}\\
&= \dfrac{(1-x)^2}{1-3x}\\
\end{align}
$
From the line labeled "$(*)$",
$F_n 
= 3^n-2\ 3^{n-1}+3^{n-2}
= 3^{n-2}(9-6+1)
= 4\ 3^{n-2}
$.
