Identity for this recursive relation with multiple terms I have a recursive relation algorithm which is defined as follows:
$$F_n = 3(F_{n-1} - F_{n-2}) + F_{n-3}$$
$$F_0 = 0$$
$$F_1 = 1$$
$$F_2 = 4$$
From calculating the first few values, I know this is equivalent to $F_n = n^2$, however I don't quite know how to derive that. I tried substituting and telescoping, but I couldn't find an appropriate pattern.
How would I do this?
 A: You've conjectured that $F_n=n^2$ for all $n.$ You know it is true for $n=0,1,2,$ and if you happen to know that $F_k=k^2$ for $k=n-1,n-2,n-3,$ then since $$F_{n-1}-F_{n-2}=(n-1)^2-(n-2)^2=\bigl((n-1)+(n-2)\bigr)\bigl((n-1)-(n-2)\bigr)=2n-3,$$ we have $$F_n=3(F_{n-1}-F_{n-2})+F_{n-3}=6n-9+(n-3)^2=6n-9+n^2-6n+9=n^2.$$ Hence, by (strong) induction, we're done.

How can one derive this, though (aside from guessing)?
Well, subtracting $2F_{n-1}-F_{n-2}$ from both sides of the recurrence relation yields $$F_n-2F_{n-1}+F_{n-2}=F_{n-1}-2F_{n-2}+F_{n-3},$$ or equivalently, $$F_n-2F_{n-1}+F_{n-2}=F_{n-1}-2F_{(n-1)-1}+F_{(n-1)-2}.\tag{$\star$}$$ This shows that there is some constant $c$ such that $$F_n-2F_{n-1}+F_{n-2}=c\tag{$\heartsuit$}$$ for all $n$, which is very readily proved from $(\star)$ by induction. In particular, letting $n=2$ shows us that $c=4-2\cdot 1+0=2.$ Hence, adding $F_{n-1}-F_{n-2}$ to both sides of $(\heartsuit)$ and making the substitution $c=2$ shows us that $$F_n-F_{n-1}=F_{n-1}-F_{n-2}+2$$ for all $n,$ meaning that the difference between subsequent terms increases by $2$ every time. So, $F_1-F_0=1,$ then $F_2-F_1=3,$ $F_3-F_2=3,$ etc. In general, we have $F_k-F_{k-1}=2k-1$ for all $k\ge1.$ Recalling/observing that $$\sum_{k=0}^n(2k-1)=n^2$$ for all $n\geq1,$ we're done.
A: General solution of this recursion is of the form $$F_n =A +Bn +Cn^2 $$ where $A,B,C\in\mathbb{R} .$
A: $\newcommand{\+}{^{\dagger}}%
 \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{\down}{\downarrow}%
 \newcommand{\ds}[1]{\displaystyle{#1}}%
 \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}%
 \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{\isdiv}{\,\left.\right\vert\,}%
 \newcommand{\ket}[1]{\left\vert #1\right\rangle}%
 \newcommand{\ol}[1]{\overline{#1}}%
 \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]{\,#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}$
Let's $\ds{{\cal F}\pars{z} \equiv \sum_{n = 0}^{\infty}F_{n}z^{n}}$

$$
\sum_{n = 3}F_{n}z^{n}
=
3\sum_{n = 3}^{\infty}F_{n-1}z^{n} - 3\sum_{n = 3}^{\infty}F_{n - 2}z^{n}
+ \sum_{n = 3}^{\infty}F_{n - 3}z^{n}
$$

$$
{\cal F}\pars{z} - F_{0} - F_{1}z - F_{2}z^{2}
=
3\sum_{n = 2}^{\infty}F_{n}z^{n + 1} - 3\sum_{n = 1}^{\infty}F_{n}z^{n + 2}
+ \sum_{n = 0}^{\infty}F_{n}z^{n + 3}
$$

$$
{\cal F}\pars{z} - z - 4z^{2}
=
3z\bracks{{\cal F}\pars{z} - z} - 3z^{2}{\cal F}\pars{z}
+ z^{3}{\cal F}\pars{z}
$$

\begin{align}
{\cal F}\pars{z} &= {-z^{2} - z \over z^{3} - 3z^{2} + 3z - 1}
= -\,{\bracks{\pars{z - 1} + 1}\bracks{\pars{z - 1} + 2}\over \pars{z - 1}^{3}}
= {\pars{1 - z}^{2} - 3\pars{1 - z} + 2\over \pars{1 - z}^{3}}
\\[3mm]&= {\pars{1 - z}^{2} - 3\pars{1 - z} + 2\over \pars{1 - z}^{3}}
={1 \over 1 - z} - {3 \over \pars{1 - z}^{2}} + {2 \over \pars{1 - z}^{3}}
\end{align}

$$
{1 \over 1 - z} = \sum_{n = 0}^{\infty}z^{n}\,,\quad
{1 \over \pars{1 - z}^{2}} = \sum_{n = 0}^{\infty}\pars{n + 1}z^{n}\,,\quad
{1 \over \pars{1 - z}^{3}} = \half\sum_{n = 0}^{\infty}\pars{n + 1}\pars{n + 2}z^{n}
$$

\begin{align}
{\cal F}\pars{z}&=
\sum_{n = 0}^{\infty}\bracks{1 - 3\pars{n + 1} + \pars{n + 1}\pars{n + 2}}z^{n}
=\sum_{n = 0}^{\infty}\color{#00f}{\large n^{2}}z^{n}
=\sum_{n = 0}^{\infty}\color{#00f}{\large F_{n}}z^{n}
\end{align}

$$\color{#00f}{\large F_{n}} = \color{#00f}{\large n^{2}}$$

A: Proof
We want to show that $F_n = n^2$ for all $n \geq 0$. This is clearly true for $n=0,1,2$ since $F_0=0, F_1=1, F_2=4$. For $F_3$, we get that $F_3 = 3(F_2-F_1)+F_0 = 3(4-1)+0 = 9 = 3^2$. So it is true for $n=3$.
Assume for some $k\geq 3$ that $F_i = i^2$ for all $i \leq k$. We want to show that $F_{k+1} = (k+1)^2$. By the recurrence relation, $F_{k+1} = 3(F_k-F_{k-1})+F_{k-2}$. By the inductive hypothesis, we know that $F_k = k^2, F_{k-1} = (k-1)^2, F_{k-2}=(k-2)^2$. So 
$\begin{align}
F_{k+1} &= 3(k^2-(k-1)^2)+(k-2)^2 \\
&= 3[k^2-(k^2-2k+1)]+(k^2-4k+4) \\
&= 3(2k-1)+k^2-4k+4 \\ 
&= 6k-3+k^2-4k+4 \\
&= k^2+2k+1 = (k+1)^2
\end{align}$
