Find least $\lambda$ for which recursive sequence is always positive

Question

Find the least $\lambda$ for which the sequence $\{b_n\}$ defined by $b_1=1$, $b_2=\lambda-1$ and $b_{n+2}=\lambda(b_{n+1}-b_n)$ is always positive.

I guess $\lambda=4$, which yields $b_n=2^{n-1}(n+1)$. This indeed works. For $\lambda=3.9$, I used Python to disprove.

l=3.9
a=1
b=2.9
for i in range(20):
    c=l*(b-a)
    a=b
    b=c
print(a,b)

I also found that $\lambda=4$ is the least parameter for which the quadratic $x^2-\lambda(x-1)$ has real roots.

Actually I find the question here. But the solution seems too tricky. I want to find a more natural one.

Answer 1

The "natural" approach by just pushing our brute force way through.
For simplicity of typing, let $ \lambda = L$.

The solutions to the characteristic equation $x^2 - Lx + L = 0 $ are $ \alpha = \frac{L+ \sqrt{(L-4)L}}{2}$ and $ \beta = \frac{L- \sqrt{(L-4)L}}{2}$.
We have $ \alpha + \beta = L, \alpha\beta = L, \alpha - \beta = \sqrt{ (L-4)L}$.
The solutions to the recurrence relation is of the form $b_n = A\alpha^n + B\beta ^n$.
The initial conditions are $b_0 = \frac{1}{L}$ (Check this!), $b_1 = 1$.
So we want to solve for $ \frac{1}{L} = A + B , 1 = (A+B) \frac{L}{2} + (A-B) \frac{\sqrt{(L-4)L}}{2}$.
Solving this system gives $A+B = \frac{1}{L}$ and $ A-B = \frac{1}{\sqrt{(L-4)L}}$, or that $A = \frac{ \sqrt{L} + \sqrt{L-4} } {2 L \sqrt{L - 4} }$ and $B = \frac{ - \sqrt{L} + \sqrt{L-4} } {2 L \sqrt{L - 4} }$.
Hence $ b_n = \frac{1}{2L \sqrt{L-4}} [\sqrt{L-4} (\alpha^n + \beta^n) + \sqrt{L} (\alpha^n - \beta^n)]$, which OP stated in the comments.
This can be further simplified to

$$b_n = \frac{1}{2}[ \frac{(\alpha^n + \beta^n)}{\alpha+\beta} + \frac{(\alpha^n - \beta^n)}{\alpha-\beta}] = \frac{\alpha^{n+1} - \beta^{n+1}}{\alpha^2 - \beta^2} . $$

Observing that $b_{2^k-1} = (\alpha^{2^k} + \beta^{2^k}) b_{2^{k-1} -1} = \prod_{j=1}^k (\alpha^{2^j} + \beta^{2^j}) $, we choose to focus on $c_k = (\alpha^{2^k} + \beta^{2^k}) $ and show that this sequence isn't always positive, which would then yield the desired negative $b_n$.

Proof by contradiction. Suppose $c_k$ is always positive.
We have $c_{k+1} = c_k^2 - 2L^{2^k}$, which gives $c_{k+1} - 2L^{2^k} = ( c_k - 2L^{2^{k-1} } ) ( c_k + 2L^{2^{k-1} }) = (c_1 - 2L) \prod_{j=1}^k ( c_j + 2L^{2^{j-1} }) $.
Notice that $c_1 - 2L = L^2 - 4L < 0$.
Since $c_k$ is always positive, thus $\prod_{j=1}^k ( c_j + 2L^{2^{j-1} }) > \prod_{j=1}^k ( 2L^{2^{j-1} }) = 2^k L^{2^k - 1 } $.
Then, for a large enough $K$, $2^K (4L-L^2) > 2L$, which would give $c_{K+1} - 2L^{2^K} = (c_1 - 2L) \prod_{j=1}^k ( c_j + 2L^{2^{j-1} }) < - 2L^{2^K}$, which results in $c_{K+1} < 0 $ as desired.

Thus, we have the stronger statement that eventually one of $b_{2^k - 1}$ is negative.

Answer 2

Claim: For $\lambda < 4$, the sequence (for any positive starting values) is eventually negative.

Suppose not. Let $ c_n = \frac{b_{n+1}}{b_{n} }$, which is always positive.
The condition transforms to $c_{n+1} + \frac{\lambda}{c_{n}} = \lambda $.
Thus we have $\lambda \geq 2\sqrt{ \lambda}\sqrt{ \frac{ c_{n+1}} { c_{n}}}$, or that $ 1 > \frac{\lambda}{2\sqrt{\lambda}} \geq \sqrt{ \frac{ c_{n+1}} { c_{n}}}$, so $c_n$ is a decreasing sequence.
We also have $c_n > 1$ from the condition.
Thus, $c_n$ is a decreasing sequence that is bounded below, so it has a limit, which we denote by $c^*$.
However, there are no real solutions to $c^* + \frac{\lambda}{c^*} = \lambda $, which is a contradiction.

Answer 3

I have previously described in detail a general solution for every sequence of the form $f_n=af_{n-1}+bf_{n-2}$ with arbitrary $f_0,f_1$. The solution can be expressed as

$$ f_n=\left(f_1-\frac{af_0}{2}\right) \frac{\alpha^n-\beta^n}{\alpha-\beta}+\frac{af_0}{2} \frac{\alpha^n+\beta^n}{\alpha+\beta} $$

where $\alpha,\beta=(a\pm\sqrt{a^2+4b})/2$.

What is happening in your problem is that when $\lambda<4$, $\alpha$ and $\beta$ are complex, and moreover they are conjugates. Consider that $\alpha,\beta=re^{\pm i\theta}$, then

$$ \frac{\alpha^n-\beta^n}{\alpha-\beta}=\frac{r^n(e^{in\theta}-e^{-in\theta})}{r(e^{i\theta}-e^{-i\theta})}=\frac{r^n\sin n\theta}{r\sin \theta}\\ \frac{\alpha^n+\beta^n}{\alpha+\beta}=\frac{r^n(e^{in\theta}+e^{-in\theta})}{r(e^{i\theta}+e^{-i\theta})}=\frac{r^n\cos n\theta}{r\cos \theta} $$

Then the solution can be expressed as

$$ \begin{align} &f_n=(A\sin n\theta+B\cos n\theta)r^n\\ &B=f_0\\ &A=\frac{f_1/r-f_0\cos\theta}{\sin\theta} \end{align} $$

So the solution is seen to periodic with $\pm$-terms and that's why the outcome can only be positive when $\lambda\ge4$.