Simple Finite Continued Fraction

Question

I am working on my senior thesis and have encountered, unexpectedly, a finite continued fraction that I would be interested in resolving. I already know the answer (by an informed guess based on where the problem came from) but I was hoping that there was a less magic solution.

Unfortunately, my web searches turned up very little on continued fractions of the finite variety, so I was hoping that someone might be able to help me or at least point me toward some theory.

Anyway, the problem is probably about as simple as one could hope for in this area: given an indeterminate $\lambda$, what are the roots of $$\lambda + \frac{1}{\lambda+\frac{1}{\lambda+\frac{1}{\cdots\,\lambda}}}$$ where there are $n$-many $\lambda$s in the expression?

EDIT: Some combinatorial considerations show that the numerator of this expression is $$\sum_k \binom{n-k}{k}\lambda^{n-2k}.$$

I know that the roots of this are all the numbers of the form $2i\cos\frac{k\pi}{n+1}$ for $1\leq k\leq n$, but only because of that magic guess from above.

Answer 1

Here is the outline of a method with no magic guesses. I deliberately omit some computationals details here, but I can be more specific if you ask.

In your context it is natural to consider the sequence defined by $u_1=\lambda, \ u_{n+1}=f(u_n)$ where $f(z)=\lambda+\frac{1}{z}$. Then, what you are looking for is solutions to the equation $u_{n}=0$. Now the map $f$ is homographic, and may be viewed as the action of a particular $2\times 2$ matrix (namely $A=\left(\begin{array}{cc} \lambda & 1 \\ 1 & 0\end{array}\right)$) on $\mathbb C$.

To find a nice expression for $A^n$, one naturally looks for the eigenvalues of $A$, $\alpha$ and $\beta$. We now have three variables : $\lambda,\alpha$ and $\beta$ but luckily they can all be expressed in terms of $\alpha$ : $\beta=-\frac{1}{\alpha},\lambda=\alpha-\frac{1}{\alpha}$.

The standard change of basis computation technique shows that $A^n$ is of the form

$$A^{n-1}=\left(\begin{array}{c|c} c_1=\alpha^{n+1}+(-\frac{1}{\alpha})^{n-1} & c_2=\alpha^{n}+(-\frac{1}{\alpha})^{n-2} \\\hline\\ \ldots & \ldots \end{array}\right)$$

So $u_{n}$ can be written as a fraction whose numerator is $c_1\lambda+c_2=\alpha^{n+2}+(\frac{-1}{\alpha})^n$. This is zero iff $\alpha^{2(n+1)}=(-1)^n$, which implies that $\alpha$ is always a $4(n+1)$-th root of unity (and a $2(n+1)$-th root of unity when $n$ is even). It is easy to recover your cosines from here.

Answer 2

you have the recurrence relation $$a_{n+1} = za_n + a_{n-1}, a_0 = 1, a_1 = z, a_2 = z^2 + 1, a_3 = z^3 + 2z, a_4=z^4 + 3z^2 + 1,\cdots$$

we will define another sequence $b_n,$ polynomials of degree $n,$ by the recurrence relation $$b_{n+1} = xb_n - b_{n-1}, b_0 = 1, b_1 = x, b_2 = x^2 - 1, b_3 = x^3 - 2x,x^4 - 3x^2 + 1\cdots \tag 1$$

claim 1: $$b_n(iz) = ka_n, k = \pm 1, \pm i.$$

it is easier to find the zeros of $b_n.$ they are real and have the interlacing property that the zeros $b_{n+1}$ are separated by the zeros of $b_n.$

claim 2: $$ \text{ the zeros of } b_n \text{ are } 2\cos \left(\dfrac{j\pi}{n+1}\right), j = 1, 2, \cdots, n $$

proof: first we make a change of variable from $x$ to $t$ by $$x = 2\cos t.$$ we have the linear difference equation $$b_{n+1} = x b_n - b_{n-1}.$$ we will try solutions of the form $$b_n = \lambda^n$$ and determine the value of $\lambda$ from its characteristic equation $$\lambda^2 - 2\lambda \cos t \, + 1 = 0 .$$ therefore $$\lambda = \cos t \pm i \sin t, \, \lambda^n = \cos nt \pm i \sin nt $$ and both $\sin nt$ and $\cos nt$ satisfy the recurrence relation. so will any any linear combination of them.

we need to satisfy the initial conditions $b_0 = 1, b_1 = x = 2\cos t.$

let $b_n = A\cos nt + B\sin nt.$ then we have $$A= 1, 1 + B \sin t = 2 \cos t \implies A = 1,\, B =\frac{\cos t}{\sin t}, b_n = \frac{\sin(n+1)t}{\sin t} $$

therefore we have proved that $$b_n = \frac{\sin (n+1)t}{\sin t} \text{ is the unique solution of } (1) \text{ and the claim 2 follows. }$$

the roots of the original polynomials are then $2i\cos \left(\dfrac{j\pi}{n+1}\right), j = 1, 2, \cdots, n.$

---

$\bf edit:$ i will explain where the change of variables from $x$ to $t$ by $$x = 2 \cos t$$ in the solution of the recurrence relation $$b_{n+1} = x b_{n} - b_{n-1}, b_0 = 1, b1 = x$$ might come from. it mimics the proof of gersgorin circle theorem about the eigenvalues of a matrix.

consider the tridiagonal matrix $$A = \pmatrix{0&1&0&0\\1&0&1&0\\0&1&0&1\\0&0&1&0} $$ let $\lambda$ be an eigenvalue and the corresponding nonzero eigenvector is $\pmatrix{b_0&b_1&b_2&b_3}^T$ then we have $$b_1 = \lambda b_0, b_2 = \lambda b_1 - b_0, b_3 = \lambda b_2 - b_1 \tag 2$$

claim: $b_0 \neq 0.$ proof: if $b_0 = 0,$ then $b_1 = b_2= b_3 = 0$ contradicting the fact that $(b, b_1, b_2, b_3)$ is nonzero. therefore $b_0 = 1, b_1 = \lambda, b_2 = \lambda^2- 1, b_3 = \lambda^3 - 2\lambda$ and the eigenvalue $\lambda$ satisfies $ b_4 = \lambda b_3 - b_2 = \lambda^4 - 3 \lambda^2 + 1 = 0$

now we will show that any eigenvalue $\lambda$ of $A$ must satisfy $$ |\lambda| \le 2.$$ since an eigenvector is nonzero, there is $j$ such that $b_j, 0 \le j \le 3$ has the maximum positive absolute value.

if $j = 0,$ then $|\lambda| \le 1.$ otherwise we have $$\lambda = \frac{b_j +b_{ j-1}}{b_j} \to \big|\lambda\big| \le \Big|\frac{b_{j+1}}{b_j}\Big| + \Big|\frac{b_{j- 1}}{b_j}\Big| \le 2.$$ therefore we can write $$\lambda = 2 \cos t $$