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$?
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.
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)$$
$\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}
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$.)
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)$$
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$$
