This morning I decided to give a try on some math tests from the final of a textbook for $9^\text{th}$ graders, just "for fun" (this year I'm passing to the $10^\text{th}$ grade). It seems like it wasn't fun at all. I stumbled upon another problem that I believe can be solved using Newton's sums / Vieta's formulas and since these topics pop up so often in my problems I decided to go full documentation mode on them (I didn't understand a thing from the class).
I got to the conclusion that an equation is actually a recurrence generator so I thought of the reverse processing – looking at a recurrence through an equation. The formula I arrived at is close to the formula explained very friendly here, but in my deduction it only works for a particularization of the initial terms. I wrote this document that I wish to add to my math portfolio, but it's incomplete (I apologize if the translations are inaccurate). The next subsection would be 3.3 Proof of the generalized formula. But I don't know how to continue from there. Everywhere on the internet I see something like:
There's a general theorem that says $f(n)=Ar_1^n+Br_2^n$ where $r_1,r_2$ are roots of the equation […] and $A,B$ can be calculated through a system of linear equations […]
But I want the proof. And I don't even want to think of induction. I think induction is an excuse to not actually think the problem the way it is meant to be thought. It would be nice if people could timetravel in the future, find the formula, then go back in time and say "I've found the formula but hey let's prove it by induction because who cares about the logic." I only agree with induction when the formula is intuitive and you want to make sure that it's correct, but here's not the case.
I think I am really close to proving the formula. Basically the problem turns to:
Knowing the formula for $f(n)=c_1f(n-1)+c_2f(n-2)$ with $f(0)=2,f(1)=c_1$, find the formula for $f(n)$ for any given $f(0),f(1)$.
Again, I can't find anything on the internet and I don't want induction, nor calculus (I read that solving recurrence relations is similar to solving differential equations but I don't know calculus).
Thanks in advance!
Best Answer
Expanding on my comments under OP's question, suppose we do not know about the characteristic polynomial, and do not have the foresight to try to find solutions in the form of a geometric progression. Then the $2^{nd}$ order recurrence can still be solved by reducing it to the known case of a $1^{st}$ order recurrence $g_n = \mu g_{n-1}$ which is easily solved by telescoping as $g_n = \mu g_{n-1}=\mu^2g_{n-2}=\dots=\mu^ng_0\,$.
Let the $2^{nd}$ order homogeneous recurrence be $f_n=a f_{n-1}-bf_{n-2}$. We can assume WLOG that $b\ne0$, otherwise it would not be a $2^{nd}$ order recurrence.
The idea is to try to rewrite the relation $f_n=a f_{n-1}-bf_{n-2}$ in the form $g_n = \mu g_{n-1}$ where $g_n=f_n-\lambda f_{n-1}$ is a linear combination between consecutive terms of the original sequence:
$$ g_n = \mu g_{n-1} \;\iff\; f_n - \lambda f_{n-1} = \mu(f_{n-1}-\lambda f_{n-2}) \;\iff\; f_n = \color{red}{(\lambda+\mu)}\,f_{n-1}- \color{green}{\lambda\mu}\, f_{n-2} $$
The last equality matches $f_n=\color{red}{a} f_{n-1}-\color{green}{b}f_{n-2}$ if we choose $\lambda,\mu$ such that $\lambda+\mu=a$ and $\lambda\mu = b$ $\;\left(\dagger\right)\;$ with $\lambda,\mu \ne 0$ because $b \ne 0$.
Then $g_n=\mu^{n-1} g_1\,$, and $f_n$ can be determined by adding the following and telescoping again:
$$ \begin{cases} f_n - \lambda f_{n-1} &= \mu^{n-1}\,g_1 && \mid \,\cdot\,1 \\ f_{n-1} - \lambda f_{n-2} &= \mu^{n-2}\,g_1 && \mid \,\cdot\, \lambda \\ f_{n-2} - \lambda f_{n-3} &= \mu^{n-3}\,g_1 && \mid \,\cdot\, \lambda^2 \\ \dots \\ f_2 - \lambda f_1 &= \mu \,g_1 && \mid \,\cdot\, \lambda^{n-2} \\ f_1 - \lambda f_0 &= \;\;\,g_1 && \mid \,\cdot\, \lambda^{n-1} \end{cases} $$
$$ \implies\;\;\;\;f_n = \lambda^n f_0 + \underbrace{\left(\lambda^{n-1}+\lambda^{n-2}\mu+\dots+\mu^{n-1}\right)}_{=\;\begin{cases}\begin{align} (\lambda^n-\mu^n)/(\lambda-\mu) && \text{if}\;\; \lambda \ne \mu \\ n\,\lambda^{n-1} && \text{if}\;\; \lambda = \mu\end{align}\end{cases}}\,\left(f_1-\lambda f_0\right) $$
$\;\left(\dagger\right)$ Note that, by Vieta's relations, these $\lambda, \mu$ are the roots of the quadratic $t^2 - at + b = 0$, which "happens" to be the characteristic polynomial associated with the original recurrence.