1

Original Question. Part 1Original Question. Part 2.Hi i just have a quick question. I have a question for my assignment which asks for a(n). I believe I have solved for a(n) and it is $$ a_n = 7a_{n-2} + 14a_{n-3}$$ (the question asks specifically to solve it in terms of n-2 and n-3)

so I have that statement and now it is asking me to prove by induction that a(n)<=3.8^n for all n=>2.

I figured the basic induction step but I can't seem to find how to expand it or substitute a(k) into a(k+1) statement during the induction step.

sorry I should have mentioned that a(1) = 7, a(2) = 14, a(3) = 49, a(4) = 196 for n=>4. and a(0) = 0

Grammer
  • 11

3 Answers3

1

For the induction step, we need to show

$$a_{n+1} = 7a_{n-1} + 14a_{n-2} \le 3.8^{n+1}$$

Let $\alpha = 3.8$. Then, provided that

$$ a_{n-2} = 7a_{n-4} + 14a_{n-5}\le \alpha^{n-2}$$ $$ a_{n-1} = 7a_{n-3} + 14a_{n-4}\le \alpha^{n-1}$$ $$ a_n = 7a_{n-2} + 14a_{n-3}\le \alpha^n$$

we could complete the induction step by

$$a_{n+1} = 7a_{n-1} + 14a_{n-2}\le 7(\alpha^{n-1})+14(\alpha^{n-2})=\Big(\frac{7}{\alpha}+\frac{14}{\alpha^2}\Big)\alpha^n$$

which would imply that

\begin{align}\Big(\frac{7}{\alpha}+\frac{14}{\alpha^2}\Big)\le \alpha &\implies 7\alpha+14\leq \alpha^3 \\&\implies\alpha^3-7\alpha-14\ge 0\\&\implies \alpha\ge\frac{1}{3}\sqrt[3]{189-42\sqrt{15}}+\frac{\sqrt[3]{7\big(9+2\sqrt{15}}\big)}{3^{2/3}}\\&\implies \alpha \ge 3.34454 \end{align}

therefore as we are given that $\alpha=3.8$ it follows that

$$a_{n+1} = \Big(\frac{7}{\alpha}+\frac{14}{\alpha^2}\Big)\alpha^n \leq 3.8^{n+1}$$

Axion004
  • 10,056
  • FOR BONUS MARKS part:

    $$\frac{7}{3.8}+\frac{14}{14.44} \approx 2.811$$

    so we could go as low as $2.82^n$.

     – Axion004 Aug 24 '19 at 04:09
  • 1
    No, $2.82$ doesn't work. In fact, if we want $a_n \le \alpha^n$ for $n \ge 2$, in the induction step we have $$a_n \le \left ( \frac 7 \alpha + \frac {14} {\alpha^2} \right) \alpha^n$$ so we must have $\alpha \ge \frac 7 \alpha + \frac {14} {\alpha^2}$, which implies $$\alpha \ge \frac 1 3 \left ( \sqrt[3] {189 - 42 \sqrt {15}} + \sqrt[3] {189 + 42 \sqrt {15}} \right ) \approx 3.34$$ But we must have also $\alpha \ge \sqrt {14} \approx 3.74$, $\alpha \ge \sqrt[3] {49} \approx 3.66$ and $\alpha \ge \sqrt[4] {196} = \sqrt {14} \approx 3.74$. So we can go as low as $\sqrt {14} \approx 3.74$. – Luca Bressan Aug 24 '19 at 11:55
  • @LucaBressan: Yes, I forgot to check to the other conditions. I have updated my answer to show that the variable $\alpha$ could be analyzed. – Axion004 Aug 24 '19 at 14:51
0

What is the value of $a_0,a_1,a_2$? It is unlikely that $a_n \le 3.8^n$ since usually $a_n = O(4.497324135953^n)$ since the real root of characteristic equation $x^3-14x-28$ is 4.497324135953

Zhaohui Du
  • 1,816
  • Hi thanks for the resposne I updated my response. – Grammer Aug 23 '19 at 11:04
  • 1
    so $a_4$ doesn't equal to $14a_2+28a_1$? – Zhaohui Du Aug 23 '19 at 11:08
  • I don't particularly agree with this answer because for example the recurrence $a_n=2a_{n-3}$ has the characteristic equation $x^3-2$ for which the only real root is $\sqrt[3]{2}$ yet the result should be that $a_n=O(2^n)\ne O((\sqrt[3]{2})^n)$. – Peter Foreman Aug 23 '19 at 11:13
  • No. Your example is still $a_n = O(2^{n/3})$ – Zhaohui Du Aug 23 '19 at 11:16
  • Usually we should use the norm of root with maximal norm. – Zhaohui Du Aug 23 '19 at 11:17
  • Sorry I must of got the first part wrong, I am just trying to resolve it now. thanks – Grammer Aug 23 '19 at 11:18
  • I posted the link to the original question. Any help would be great! – Grammer Aug 23 '19 at 11:19
  • It is easy now. First we could verify that $a_n\le 3.8^n$ for n=2,3,4 since (19:42) gp > 3.8^2 %23 = 14.440000000000000000000000000000000000 (19:42) gp > 3.8^3 %24 = 54.872000000000000000000000000000000000 (19:42) gp > 3.8^4 %25 = 208.51360000000000000000000000000000000 – Zhaohui Du Aug 23 '19 at 11:43
  • Now assume $a_{k-1}\le 3.8^{k-1}, a_{k-2}\le 3.8^{k-2} a_{k-3}\le 3.8^{k-3}$ we have $a_k=7a_{k-2}+14a_{k-3}\le 73.8^{k-2}+143.8^{k-3}=(73.8+14)3.8^{k-3}=40.63.8^{k-3}\lt 3.8^3 3.8^{k-3}=3.8^k$ – Zhaohui Du Aug 23 '19 at 11:46
  • Thanks so much, I think thats pointing me in the right direction. – Grammer Aug 23 '19 at 11:51
0

Assume the result for both $a_k$ and $a_{k+1}$.

Then $a_{k+3}$ is no greater than $7.3.8^{k+1}+14.3.8^{k}$. This sum is less than $3.8^{k+3}$, as required.