# How to solve this linear functional homogenous recurrence relation?

I recently came across finding eigenvalues of a particular tridiagonal matrix and trying to reduce the problem, I came to a recurrence relation, which I don't know how to solve: $$a_i(\lambda)=(\lambda+2)a_{i-1}(\lambda)-a_{i-2}(\lambda)\tag{i\in\{3,4,\ldots,n\}}$$ with the following boundary conditions: $$a_1(\lambda)=1,a_2(\lambda)=1+\lambda,a_{n-1}(\lambda)=(1+\lambda)a_n(\lambda)$$ Obviously each $a_i(\lambda)$ is a function in $\lambda$ I tried writing $$a_{n}(\lambda)=\sum_{i=0}^{\infty}a_{n,i}\lambda^i$$ then I got a recurrence relation in constants: $$a_{n+1,i}=a_{n,i-1}+2a_{n,i}+a_{n-1,i}$$ I thought that sum of subscripts is constant on both sides so a generating function would be suitable and thus guessed $$a_{n,i}=b_{n}c_i$$ Now we get: $$b_{n+1}c_{i}=b_nc_{i-1}+2b_nc_{i}+b_{n-1}c_{i}=b_n(c_i+c_{i-1})+c_i(b_n+b_{n-1})$$ Seeing a fibonacci type of relation I thought it would be better to simplify as: $$d_i=b_{i-1}+b_{i-2},e_i=c_{i-1}+c_{i-2}\tag{1}$$ So: $$b_{n+1}c_i=b_ne_{i+1}+c_id_{n+1}\tag{2}$$ Now we see that the sum of subscripts is constant $n+i+1$. We define generating functions by corresponding capital letters like: $$B(x)=\sum_{n=0}^{\infty}b_nx^n$$ Thus from $(1)$ and $(2)$:$$B(x)C(x)=\frac{1+x}{x^2}[B(x)C(x)-c_0B(x)-b_0C(x)]-\frac1x(b_1+c_1)\\A(x)=\frac x{1+x-x^2}[b_1+c_1+b_0C(x)+c_0B(x)]$$ We could've got $A$ if $c_0$ or $b_0$ was zero. We also need to convert the boundary conditions in new variables.

All help is appreciated.

Fix $\lambda$, and just call the value $a_n$, not $a_n(\lambda)$. You have the linear recurrence relation $$a_i = (\lambda + 2)a_{i-1} - a_{i-2}$$ The set of all sequences satisfying this relation forms a vector space (any multiple or some sequences satisfying the relation is easily seen to satisfy it as well). Since the values are completely determined by the first two elements, this vector space is of dimension 2. So if we can find two solutions, we can find all of them, including yours (yours stops at $n$, but we can use the recurrence relation to continue it). Suppose a solution of the form $r^i$ for some $r$. Then the recurrence relation becomes $$r^i = (\lambda + 2)r^{i-1} - r^{i-2}$$ Divide out the common factor and we have $$r^2 - (\lambda +2)r + 1 = 0$$ So $$r= \frac{\lambda + 2 \pm \sqrt{\lambda^2 +\lambda - 2}}2$$ which gives us two sequences. Any sequence satisfying the relation must be of the form $Ar_1^{i-1} + Br_2^{i-1}$, where $r_1, r_2$ are the two values above. (The offset of $1$ in the index will make the initial conditions easier to handle, and just changes the values of the arbitrary constants $A, B$.)
Now we know that $a_1 = 1, a_2 = 1 + \lambda$, so $$A + B = 1$$$$Ar_1 + Br_2 = 1 + \lambda$$. Solve these equations for $A$ and $B$, and you will find what your functions $a_i(\lambda)$ are.
You have one more condition listed as $a_{n-1}(\lambda) = a_n\lambda$ that I am unsure how to interpret. (Are you saying that $a_n$ is constant? That is inconsistent with your other relations.) If it is possible to meet at all, it may be that only certain values of $\lambda$ will work. Those would be the eigenvalues.
• I meant $a_{n-1}(\lambda)=(1+\lambda)a_n(\lambda)$ – RE60K Apr 14 '16 at 17:13