0

$ a_n=\left\{ \begin{array}{ll} 2 & n=1 \\ 6 & n=2 \\ a_{n-1}+9a_{n-2} & n\geq 3 \\ \end{array} \right. $

$\forall n \in N^+$, $a_n < 3^n$.

So far, I have assumed that $a_{n-1} \le (n-1)$ then, $(n-1) + 9(n-2) < 3^n$, then $10n-19 < 3^n$. Does this cover all cases where $n>3$?

Would this be a correct step to take? can anybody verify?

Raffaele
  • 26,371
user498021
  • 37
  • Oh... how would you approach this question? @fleablood – user498021 Nov 05 '17 at 20:54
  • "So far, I have assumed that $a_{n−1}≤(n−1)$" Why on earth would you assume that? $a_1 > 1-1; a_2 > 2-1; a_3 > 3-1$. So far as I can tell that is never true. So it covers none of the cases. – fleablood Nov 05 '17 at 20:55
  • I would assume $a_{k} < 3^k$ for all $k \le n$ and show therefore that $a_{n+1} < 3^{n+1}$. – fleablood Nov 05 '17 at 20:56
  • 1
    For $n\ge 5$ the statement is false: $$ \begin{array}{l|l|l} n & a_n & 3^n\ \hline 1 & 2. & 3 \ 2 & 6. & 9 \ 3 & 24. & 27 \ 4 & 78. & 81 \ 5 & 294. & 243 \ 6 & 996. & 729 \ 7 & 3642. & 2187 \ 8 & 12606. & 6561 \ 9 & 45384. & 19683 \ 10 & 158838. & 59049 \ \end{array} $$ – Raffaele Nov 05 '17 at 20:58
  • $a_{n+1} = a_n + 9a_{n-1} < 3^n + 9*3^{n-1} = 3^n + 3^{n+1}$ Hmmm... And as Raffaele points out $a_5 > 3^5$ – fleablood Nov 05 '17 at 21:02
  • You can prove $a_n > 3^n; n \ge 5$ by induction. $a_{n+1} = a_n + 9a_{n-1} > 3^n + 9*3^{n-1} = 3^n + 3^{n+1} > 3^{n+1}$ so only requires verifying that $a_5 > 3^5$ and $a_6 > 3^6$. – fleablood Nov 05 '17 at 21:06
  • @Raffaele and fleablood sorry, but if n = 10, shouldn't it be subbed into $a_{n-1}$ and $9a_{n-2}$ which equals to $a_9$ and $9a_8%$ which equals $9 + 72?$ – user498021 Nov 05 '17 at 21:24
  • @user498021 Maybe it is not clear enough to you how these recurrences work. Try to make a table by hand, just the first five/six rows and you'll soon realize the meaning of recursion – Raffaele Nov 05 '17 at 21:31
  • Ah, ok. I just did it and I see how i'm supposed to use the previous $a_n$ to find the current one. But I have a question. If $a_1$ and $a_2$ were not given this sequence we wouldn't know the recurrence right? – user498021 Nov 05 '17 at 21:43
  • @fleablood, regarding your comment of induction, 3n+9∗3n−1, How did you arrive at this step? understand all the steps up to there, then i'm lost – user498021 Nov 05 '17 at 22:05
  • @fleablood pls help :( – user498021 Nov 05 '17 at 22:44
  • I need your help fleablood. thank you. – user498021 Nov 05 '17 at 23:23
  • How can I help you prove something that is false? – fleablood Nov 05 '17 at 23:32
  • " regarding your comment of induction, $3^n+9∗3^{n−1}$". If I assume $a_{n} < 3^n$ (which it isn't). And I assume $a_{n-1} < 3^{n-1}$ (which it isn't). I would ga $a_n + 9a_{n-1} < 3^n + 93^{n-1}$. But that is not* less than $3^{n+1}$ so it will not work as an inductive step. – fleablood Nov 05 '17 at 23:38
  • yes, but how did you derive $a_n + 9a_{n-1}$ to be less than $3^n +9 *3^{n-1}$? – user498021 Nov 06 '17 at 00:11

0 Answers0