Recursion with combinatoric argument

Question

Find a recursion in the form $a_n = \lambda_1a_{n-1} + \lambda_2a_{n-2}+j$, where $\lambda_1$ and $\lambda_2$ and $j$ are integers, such that its closed form is $(n+1)^2$.

Also provide a combinatorial argument for the recursion (a counting situation that can be modeled by this recursion).

---

I tried dabbling with the characteristic equation, and working backwards through the process of finding a closed form, but I can't find such a recursion.

Let $\lambda_1$ and $\lambda_2$ be $x$ and $y$, respectively. We have $$a_n = xa_{n-1} + ya_{n-2}.$$ Let $a_n = c^n$. Then, we have $$c^n = xc^{n-1}+yc^{n-2}.$$ Dividing by $c^{n-2}$, we get $$c^2 = xc + y.$$ Now I have to find the roots, but I'm stuck.

Answer 1

To give a combinatorial argument for Peter Foreman's recursion, let $a_n$ be the number of $2$-letter words in an alphabet with $n + 1$ letters. To spell your word, you can either choose a $2$-letter word solely from the first $n$ letters in the alphabet or choose a $2$-letter word solely from the last $n$ letters in the alphabet --- amounting to $2 a_{n-1}$ ways --- but alas, we've overcounted some cases! Specifically, we've double-counted the cases where we chose our word comes exclusively from the middle $n - 1$ letters, so we must remove $a_{n - 2}$ from our total count.

We're almost there, but we've missed an edge case, because you can also choose the the first and last letters to spell your word. Since order matters, this accounts for $2$ more cases. Thus, in total we have $$a_n = 2 a_{n-1} - a_{n-2} + 2$$ verifying our answer.

Answer 2

One thing you're missing in your argument, incidentally, is that the formula you assume for $a_n$ is only for part of the solution (and for homogeneous recurrences); while $a_n=c^n$ (for the appropriate $c$) is one solution of the homogeneous equation $a_n=xa_{n-1}+ya_{n-2}$, there's another specific solution corresponding to the other root of the quadratic $t^2-xt-y=0$; if the quadratic has a double root, then the solutions are generically $(a+bn)c^n$ for some constants $a$ and $b$.

Instead, you should probably think about this problem from the other direction. Consider the 'difference' operator $Da_n$ that takes the sequence $\{a_n\}$ to the sequence $\{a_{n+1}-a_n\}$. Then much like the derivative, this operator takes a polynomial sequence to another one of lower degree; in particular, it takes a quadratic sequence to a linear one, and a linear one to a constant one. In other words, $D^2a_n$, where $a_n=(n+1)^2$, is a constant sequence. You just have to figure out how to write this as a recurrence.

As for the combinatorial proof, well, I just can't resist the pretty picture here:

Answer 3

Simply inject the closed form in your recursion formula. You will get for every $n\in\mathbb{N}$

$(n+1)^2=\lambda_1 n^2 +\lambda_2 (n-1)^2 +j$ $\Leftrightarrow n^2+2n+1=\big(\lambda_1+\lambda_2\big)n^2 + \big(-2\lambda_2\big) n + \big(\lambda_2 +j\big)$

and then you identify the coefficients to get $\lambda_1=2$, $\lambda_2=-1$ and $j=2$.