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}$


  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?

  • 1
    $\begingroup$ 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 ? $\endgroup$
    – Optidad
    Sep 3 '20 at 11:31
  • $\begingroup$ $c_1,c_2,c_3$ are all constants. Yes I want them to respect the inequality. $\endgroup$ 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. $$

  • $\begingroup$ 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$. $\endgroup$
    – Optidad
    Sep 3 '20 at 15:08
  • $\begingroup$ 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$. $\endgroup$ Sep 3 '20 at 16:39
  • $\begingroup$ @John L., all these constants may be 0. $\endgroup$
    – Optidad
    Sep 4 '20 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.