I was reading a textbook with the following recurrence example:
$$ a_n = (n-1)a_{n-1} - na_{n-2} + n-1 \quad \text{for } n > 1 \text{ with } a_0=a_1=1 $$
From the example, we set $f(n)=n-1$, so that $a_n=(n-1)a_{n-1}-na_{n-2}+f(n)$.
Using candidates $1$, $n$ and $n^2$ for $a_n$, we get the following repertoire table:
$$(1)\quad a_n=1 \quad \quad \quad \quad \quad f(n) = a_n - (n-1)a_{n-1} + na_{n-2}=2$$ $$(2) \quad a_n=n \quad \quad \quad \quad \quad f(n) = a_n - (n-1)a_{n-1} + na_{n-2}=n-1$$ $$(3) \quad a_n=n^2 \quad \quad \quad \quad \quad f(n) = a_n - (n-1)a_{n-1} + na_{n-2}=n+1$$
From the table, we already have a solution for $f(n)=n-1$, which is $(2)$, where $a_n=n$, with initial conditions $a_0=0$ and $a_1=1$.
We can also subtract $(1)$ from $(3)$ to get $a_n=n^2-1$. The linear combination of $(3)-(1)$ results in $f(n)=n-1$ as well with initial conditions $a_0=-1$ and $a_1=0$.
However, from this point on I got lost. The text says that we can combine linearly independent solutions $a_n=n$ and $a_n=n^2-1$ to get the 'right' initial values (where $a_0=a_1=1$) so that the final answer is $a_n=n^2-n+1$.
I could not figure out how the final answer is $a_n=n^2-n+1$.
$a_n=n^2-n+1$ seems to be a linear combination as well of $(3)-(2)+(1)$. But if we add them up we get $f(n)=4$ which is not $f(n)=n-1$, even though its initial values match up to $a_0=a_1=1$.
Any help?
This realtion $$a_n = (n-1)a_{n-1} - na_{n-2} + n-1 \qquad \text{for } n > 1\quad \text{ with }\quad a_0=a_1=1$$ generates interesting numbers $$\left( \begin{array}{cc} n & a_n \\ 0 & 1 \\ 1 & 1 \\ 2 & 0 \\ 3 & -1 \\ 4 & 0 \\ 5 & 9 \\ 6 & 50 \\ 7 & 243 \\ 8 & 1308 \\ 9 & 8285 \\ 10 & 61494 \\ 11 & 523815 \\ 12 & 5024048 \\ 13 & 53478993 \\ 14 & 624890250 \\ 15 & 7946278619 \\ 16 & 109195935300 \\ 17 & 1612048228293 \\ 18 & 25439293045598 \\ 19 & 427278358483215 \\ 20 & 7609502950269144 \\ 21 & 143217213477235385 \\ 22 & 2840152418116021938 \\ 23 & 59189357288576068803 \\ 24 & 1293191559602465055980 \\ 25 & 29556863498244759623469 \\ 26 & 705298606906454899131270 \\ 27 & 17539728465115218867579383 \\ 28 & 453824307564730172248967808 \\ 29 & 12198428486324103475811296545 \\ 30 & 340139696876457095631058565594 \end{array} \right)$$ A quick and dirty regression (for $ 5 \leq n \leq 30$) gives $(R^2=0.999984)$ $$\log(a_n)=0.51633\, n^{1.44998}-3.31609$$ where the parameters are highly significant. $$\begin{array}{clclclclc} \text{} & \text{Estimate} & \text{Standard Error} & \text{Confidence Interval} \\ a & -3.31609 & 0.16768 & \{-3.66384,-2.96835\} \\ b & +0.51633 & 0.01529 & \{+0.48463,+0.54803\} \\ c & +1.44998 & 0.00829 & \{+1.43278,+1.46718\} \\ \end{array}$$
Quite far away from a polynomial.
Are you sure about the equation ?