Finding a general sum formula for a recurrence relation Hey I have a general recurrence relation as follows, and I want to find a general sum formula in terms of the variable.
$U_1=DE$
$U_n=(U_{n-1} + D)E$
$D$ and $E$ are real positive numbers, can there be a sum formula for $n$ terms in terms of $D$ and $E$?
 A: Hint: 
$$U_2=EU_1+U_1=(E+1)U_1$$
$$U_3 = EU_2+U_1=(E^2+E)U_1+U_1=(E^2+E+1)U_1$$
$$U_4 = EU_3+U_1=(E^3+E^2+E)U_1+U_1=(E^3+E^2+E+1)U_1$$
Do you see a pattern? Use also $1+E+E^2+...+E^{n-1}=\frac{1-E^{n}}{1-E}$.
If you found the candidate for the formula you can plug it into the recurrence equation and test if it is right or use induction.
A: Notice the recurrence relation can be rewritten as
$$U_{n+1} = (U_n + D)E = U_n E + \frac{DE}{1-E}(1-E) \implies 
U_{n+1} - \frac{DE}{1-E} = \left(U_n - \frac{DE}{1-E}\right)E$$
After the offset $-\frac{DE}{1-E}$, each term is a multiple of $E$ of previous term. For general $n$, this leads to
$$U_n - \frac{DE}{1-E} = \left(U_1 - \frac{DE}{1-E}\right)E^{n-1}
= \left(DE - \frac{DE}{1-E}\right)E^{n-1}  = -\frac{DE}{1-E} E^n\\
\implies U_n = \frac{DE}{1-E}(1-E^n)$$
A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

With $\ds{U_{1} = DE}$:

\begin{align}
U_{n} & = \pars{U_{n - 1} + D}E \implies
U_{n} - {DE \over 1 - E} = \pars{U_{n - 1} - {DE \over 1 - E}}E =
\pars{U_{n - 2} - {DE \over 1 - E}}E^{2}
\\[5mm] & =
\pars{U_{n - 3} - {DE \over 1 - E}}E^{3} = \cdots =
\pars{U_{1} - {DE \over 1 - E}}E^{n - 1} =
\pars{DE - {DE \over 1 - E}}E^{n - 1}
\\[5mm] & = {D \over E - 1}\,E^{n + 1} \implies
U_{n} = {DE \over 1 - E} + {D \over E - 1}\,E^{n + 1} =
\bbx{DE\,{E^{n} - 1 \over E - 1}}
\end{align}
A: WLOG, $D=1$ (see why ?)
Then as there is this factor $E$, consider $U_n=V_nE^n$.
The recurrence becomes
$$V_1E=E,$$ and $$V_nE^n=(V_{n-1}E^{n-1}+1)E$$ or
$$V_n=V_{n-1}+E^{-n},$$ which is the summation of a geometric series.
$$V_n=\frac{1-E^{-n}}{1-E^{-1}},$$ and
$$U_n=\frac{E^n-1}{1-E^{-1}}.$$
Now the summation of the $U_n$ is that of another geometric series and a constant term.
$$\sum_{k=1}^n U_k=\frac{\dfrac{E^{n+1}-1}{E-1}-n}{1-E^{-1}}.$$
(Or the same times $D$.)
A: I'm always a fan of the generating function approach.
The given recurrence can be defined as $u_0=0$ and $u_n=(u_{n-1}+d)e$.
\begin{align}
U(x) &= \sum_{j=0}^{\infty}u_jx^j\\
&= \sum_{j=1}^{\infty}u_jx^j\\
&= \sum_{j=1}^{\infty}(u_{j-1}+d)ex^j\\
&= \sum_{j=0}^{\infty}(u_{j-1}+d)ex^{j+1}\\
&= ex\sum_{j=0}^{\infty}(u_{j-1}+d)x^j\\
&= ex\left(U(x)+\frac{d}{1-x}\right)\\
U(x) &= \frac{dex}{(1-x)(1-ex)}\\
\end{align}
If we set $\frac{dex}{(1-x)(1-ex)}=\frac{A}{1-x} + \frac{B}{1-ex}$ and solve for $A$ and $B$, we get that $A=\frac{de}{1-e}$ and $B=\frac{-de}{1-e}$.
\begin{align}
U(x) &= \frac{de}{(1-e)(1-x)} + \frac{-de}{(1-e)(1-ex)}\\
&= \frac{de}{1-e}\left(\sum_{j=0}^{\infty}x^j - \sum_{j=0}^{\infty}e^jx^j\right)\\
&= \frac{de}{1-e}\sum_{j=0}^{\infty}(1-e^j)x^j\\
\end{align}
The coefficient of $x^j$ is then the $j^{th}$ term in the sequence.
$$u_0=\frac{de}{1-e}(1-e^0)=0$$
$$u_1=\frac{de}{1-e}(1-e^1)=de$$
$$u_j=\frac{de}{1-e}(1-e^j)$$
A: I have previously shown here, that $f_n=Af_{n-1}+B$, which I call a short Fibonacci sequence, has the general solution
$$f_n=\frac{[(A-1)f_0+B]A^n-B}{A-1},\quad n\ge0$$
This gives us a solution, once and for all such short Fibonacci sequences. In the present case, we have $A=E,~B=DE$, and $u_1=DE$ so that
$$u_n= \frac{DE \left(E^n-1\right)}{E-1}\quad n\ge1$$
