I'm quite comfortable when it comes to simple induction. However, whenever I encounter a strong induction problem, I don't know how to approach it... Thank you for contributing.
http://puu.sh/yfFlI/be31254ac6.png
$\forall n \in N^+, t_n < 2^n$
$\begingroup$
$\endgroup$
28
-
$\begingroup$ Hint: inductively we have $t_n=t_{n-1}+t_{n-2}+t_{n-3}≤ 2^{n-1}+2^{n-2}+2^{n-3}=2^{n-3}\times \left( 4+2+1\right) $ so... $\endgroup$ – lulu Nov 6 '17 at 0:24
-
$\begingroup$ so what have you tried so far? $\endgroup$ – Vaas Nov 6 '17 at 0:24
-
$\begingroup$ @lulu how did you derive it to be exponents? What the...confused... $\endgroup$ – user498021 Nov 6 '17 at 0:26
-
$\begingroup$ I don't understand your confusion. Suppose I know the desired statement to be true for, say, $t_{17}$. What does that tell you? $\endgroup$ – lulu Nov 6 '17 at 0:28
-
$\begingroup$ If we know that $t_\color{blue}{n}<2^\color{blue}{n}$ for all $n\leq k$ then we also know that $t_{\color{blue}{x}}<2^{\color{blue}{x}}$ if $x\leq k$ as well as $t_{\color{blue}{y^2}}<2^{\color{blue}{y^2}}$ if $y^2\leq k$ and $t_{\color{blue}{n-2}}<2^{\color{blue}{n-2}}$ if $n-2\leq k$ etc... Just because the number in blue is written in a longer or more confusing fashion does not change that it is still a number, and whatever that number is is the same on the left as on the right. $\endgroup$ – JMoravitz Nov 6 '17 at 0:35
|
Show 23 more comments
