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?
On
General solution of this recursion is of the form $$F_n =A +Bn +Cn^2 $$ where $A,B,C\in\mathbb{R} .$
On
$\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}}$$
On
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}$
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.