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:

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

and

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

where 1 can be written:

$c_1a_k + ma_k$

where $m+c_1 = c_3$
which can be rewritten:

$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?
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.
$$