Determining which recursive term is bigger if they share the same definition

We are given a recursive definition:

$$a_1 = x,\\a_2=y, \\a_n= c_1a_{n-1}+c_2a_{n-2} \text{ for }n\ge3$$

where $$x,y,c_1,c_2,n$$ are natural numbers

we are to prove that $$a_n \le c_3^n$$ for all n

The base case is true

Assuming $$a_k \le c_3^k$$ is true

show $$a_{k+1} \le c_3^{k+1}$$ is true

We have:

1. $$c_3a_k \le c_3^{k+1}$$

and

1. $$a_{k+1} = c_1a_k + c_2a_{k-1}$$

where 1 can be written:

1. $$c_1a_k + ma_k$$

where $$m+c_1 = c_3$$

which can be rewritten:

1. $$c_1a_k + mc_1a_k + mc_2a_{k-1}$$

Now, 4 and 2 have the first term equal.

How can I determine whether $$mc_1a_k + mc_2a_{k-1}$$ in 4 is bigger or not than $$c_2a_{k-1}$$ in 2?

• do you have any relation between $c_1$, $c_2$ and $c_3$ ? Or are you looking for an expression of $c_3$ using $c_1$ and $c_2$ that respect the inequality ? Sep 3 '20 at 11:31
• $c_1,c_2,c_3$ are all constants. Yes I want them to respect the inequality. Sep 3 '20 at 21:40

Let $$c_3 = \max(1,x,y,c_1+c_2)$$. Then $$a_1 = x \stackrel{c_3 \geq x}\leq c_3^1$$ and $$a_2 = y \stackrel{c_3 \geq y}\leq c_3 \stackrel{c_3 \geq 1}\leq c_3^2.$$
Now suppose that $$a_{n-2} \leq c_3^{n-2}$$ and $$a_{n-1} \leq c_3^{n-1}$$. Then $$a_n = c_1 a_{n-1} + c_2 a_{n-2} \stackrel{\text{assumption}}\leq c_1 c_3^{n-1} + c_2 c_3^{n-2} \stackrel{c_3 \geq 1}\leq c_1 c_3^{n-1} + c_2 c_3^{n-1} \stackrel{c_3 \geq c_1+c_2}\leq c_3^n.$$
• Note that $x$, $y$, $c_1$, $c_2$, $c_3$ are natural numbers, then the "1" in the maximum is not needed. Also, $c_1 c_3 + c_2 \le c_3^2$ is more permissive than $c_1+c_2 \le c_3$. Sep 3 '20 at 15:08
• The bound isn't optimal anyhow. The correct rate of growth is $O(c^n)$, where $c$ is the larger root of $c^2 = c_1 c + c_2$. Sep 3 '20 at 16:39