Binary recurrence sequence in $\mathbb{Z}$

45 Views Asked by At

Let $u_n=Au_{n-1}+Bu_{n-2}$ binary recurrence sequence in $\mathbb{Z}$ and the companion polynomial $x^2-Ax-B$ has distinct zeros $\alpha,\beta$. Then for all $n \geq 0$ $$u_n= \gamma_1 \alpha^n + \gamma_2 \beta^n$$ for some $\gamma_1,\gamma_2$. Assume that $A^2+4B^2 >0$, i.e., $\alpha,\beta \in \mathbb{R}$ and that $\alpha \neq \pm \beta$. Assume further that we have $\gamma_1\gamma_2 \neq 0$. Prove that there are effectively computable numbers $c>0$, $n_0$ such that $$|u_n| \geq c \max(|\alpha|,|\beta|)^n$$ for $n \geq n_0$.

Assume $|\beta|=\max(|\alpha|,|\beta|) >0 $ then $$|u_n|=|\gamma_1\alpha^n + \gamma_2 \beta^n|=|\beta|^n\cdot|\gamma_1\left(\dfrac{\alpha}{\beta}\right)^n+\gamma_2|$$ However, I cannot indicate the term $|\gamma_1\left(\dfrac{\alpha}{\beta}\right)^n+\gamma_2| >c$ for some constant $c>0$.

1

There are 1 best solutions below

2
On BEST ANSWER

Note that $ \left |\left (\dfrac{\alpha}{\beta} \right )^n\right | \to _{n\to \infty} 0$, and therefore you can make it as small as you want for large values of $n$, and you can get as closer as you want to $|\gamma_2|$ (which is positive).