Solving Linear Recursion with backtracking

Question

What am I doing wrong? Is there a missing step?

Tried googling but cannot seem to get it.

Question: $$\begin{align} a_{n} &= a_{n-1}+2n+3 ,\\ a_{0} &= 4 \end{align}$$

Things I did:

$$\begin{align} a_{n}&=a_{n-1}+2n+3\\ &= (a_{n-2}-2n+3) +2n+3\\ &= (a_{n-3}-2n+3) + 2(2n) + 3(3)\\ &...\\ &...\\ \end{align}$$

Then I got:

$$\begin{align} a_n &= 2n^2 + 3n + 4 \end{align}$$

Answer 1

I think this is what you are attempting:

$$\begin{align} a_n &= a_{n-1} + 2n + 3 \\ &= (a_{n-2} + 2(n-1) + 3) + 2n + 3 &&= a_{n-2} + (2 + 2)n + 3 + 3 - 2 \\ &= (a_{n-3} + 2(n-2) + 3) + (2 + 2)n + 3 + 3 - 2 &&= a_{n-3} + (2\cdot 3)n + 3\cdot 3 - 2 - 4 \\ &= (a_{n-4} + 2(n-3) + 3) + (2\cdot 3)n + 3\cdot 3 - 2 - 4 &&= a_{n-4} + (2\cdot 4)n + 3\cdot 4 - 2 - 4 - 6 \\ &= (a_{n-5} + 2(n-4) + 3) + (2\cdot 4)n + 3\cdot 4 - 2 - 4 - 6 &&= a_{n-5} + (2\cdot 5)n + 3\cdot 5 - 2 - 4 - 6 - 8 \\ &= \dots &&= \dots \end{align}$$

Can you see the pattern yet? $a_n = a_{n-k} + \text{something}$

Use the observation from "backtracking" to guess what that $\text{something}$ is.

Answer 2

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$

$\ds{a_{0}\ =\ 4}$. With $\ds{\verts{z}\ <\ 1}$:

\begin{align} {\cal F}\pars{z}&\equiv\sum_{n\ =\ 1}^{\infty}a_{n}z^{n} =\sum_{n\ =\ 1}^{\infty}a_{n - 1}z^{n} + 2\sum_{n\ =\ 1}^{\infty}nz^{n} + 3\sum_{n\ =\ 1}^{\infty}z^{n} \\[5mm]&=\sum_{n\ =\ 0}^{\infty}a_{n}z^{n + 1} + {2z \over \pars{1 - z}^{2}} + {3z \over 1 - z} =z\bracks{a_{0} + {\cal F}\pars{z}} + {2z \over \pars{1 - z}^{2}} + {3z \over 1 - z} \\[5mm]\imp\ \pars{1 - z}{\cal F}\pars{z}&= 4z + {2z \over \pars{1 - z}^{2}} + {3z \over 1 - z} \\[5mm]\imp\ {\cal F}\pars{z}&={4z \over 1 - z} + {2z \over \pars{1 - z}^{3}} + {3z \over \pars{1 - z}^{2}} \\[5mm]&=\sum_{n\ =\ 0}^{\infty}4z^{n}+ 3\sum_{n\ =\ 2}^{\infty}n\pars{n - 1}z^{n - 1} + 3\sum_{n\ =\ 1}^{\infty}nz^{n} \\[5mm]&=\sum_{n\ =\ 0}^{\infty}4z^{n}+ 3\sum_{n\ =\ 1}^{\infty}\pars{n + 1}nz^{n} + 3\sum_{n\ =\ 1}^{\infty}nz^{n} \\[4mm]&=4 + 9z + \sum_{n\ =\ 2}^{\infty}\bracks{4 + \pars{n + 1}n + 3n}z^{n} \end{align}

Then, $$\color{#66f}{\large% a_{0}=4\,,\quad a_{1}=9\,,\quad a_{n}=4 + \pars{n + 1}n + 3n =n^{2} + 4n + 4\,,\ n \geq 2} $$

Answer 3

$$a_n=a_{n-1}+2n+3$$ $$a_{n-1}=a_{n-2}+2(n-1)+3$$ $$......$$ $$a_1=a_0+2\cdot1+3$$ adding both sides respectively yields $$a_n+(a_{n-1}+...+a_1)=(a_{n-1}+...+a_1)+a_0+2\cdot(n+(n-1)+...+1)+3\cdot n$$ $$a_n=a_0+2\cdot \frac{n(n+1)}{2}+3\cdot n=4+n^2+4n$$ for all $n\geq0$.