0

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$

user498021
  • 37
  • 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... – lulu Nov 06 '17 at 00:24
  • so what have you tried so far? – Vaas Nov 06 '17 at 00:24
  • @lulu how did you derive it to be exponents? What the...confused... – user498021 Nov 06 '17 at 00:26
  • I don't understand your confusion. Suppose I know the desired statement to be true for, say, $t_{17}$. What does that tell you? – lulu Nov 06 '17 at 00:28
  • 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. – JMoravitz Nov 06 '17 at 00:35
  • @lulu what do you mean by x (4 + 2 + 1)? – user498021 Nov 06 '17 at 01:39
  • $a \times b$ stands for the multiplication $ab$, so $2\times 3 = 6$ – lulu Nov 06 '17 at 01:46
  • I am aware of that xD But where did you get (4 + 2 + 1)? – user498021 Nov 06 '17 at 01:56
  • @lulu Pls clarify. I'm going crazy cos I can't wrap my head around it – user498021 Nov 06 '17 at 02:10
  • Just go slowly. Do you understand why I was able to write (inductively) that $t_{n-1}+t_{n-2}+t_{n-3}≤2^{n-1}+2^{n-2}+2^{n-3}$? – lulu Nov 06 '17 at 02:14
  • Yes, it's because of $t_{n-1} = 2^{n-1}$ – user498021 Nov 06 '17 at 02:15
  • We, $≤$ not $=$ But ok. Now do you understand that $2^{n-1}=2^{n-3}\times 2^2$? – lulu Nov 06 '17 at 02:16
  • Yes, you're just manipulating the exponent laws – user498021 Nov 06 '17 at 02:16
  • Exactly. And similarly $2^{n-2}=2^{n-3}\times 2^1$. It follows that $2^{n-1}+2^{n-2}+2^{n-3}=2^{n-3}\times 2^2+2^{n-3}\times 2^1+2^{n-3}\times 1=2^{n-3}\times (2^2+2^1+1)=2^{n-3}\times (4+2+1)$ – lulu Nov 06 '17 at 02:18
  • Ah. So $t_n <= 7(2^{n-3})$ How do I go from here? Do I show that it's a divisor or something? – user498021 Nov 06 '17 at 02:26
  • Well, $t_n≤7\times 2^{n-3}<8\times 2^{n-3}=2^3\times 2^{n-3}=2^n$ – lulu Nov 06 '17 at 02:30
  • I crie, I don't understand how you went from 7 to 8... but the rest is clear to me. – user498021 Nov 06 '17 at 02:32
  • Unless you're just trying to show taht a multiple of 8 is larger than 7, but isn't it best to keep the number as low as possible for proofs to work? edit: I'm just not thinking good today... ignore my above comment. Thank you lulu – user498021 Nov 06 '17 at 02:33
  • $7 < 8$. So, $7\times a < 8\times a$ for any positive $a$. – amsmath Nov 06 '17 at 02:33
  • @user498021 That's right. But when you finish, you can estimate to whatever you want. Main thing is it matches what you are looking for. And here it perfectly does. – amsmath Nov 06 '17 at 02:34
  • "isn't it best to keep the number as low as possible for proofs to work" not always. The tighter you keep the bounds, the more you can conclude, however by relaxing the bounds you can sometimes show things much more easily and naturally. So long as what you intend to show can still be shown from the relaxed bounds you are fine. – JMoravitz Nov 06 '17 at 02:36
  • Just one more question. This would prove the claim correct for all cases where n>= 1 if I used induction – user498021 Nov 06 '17 at 02:36
  • I am proving the statement you asked for. Could it be strengthened? Oh, absolutely! $t_{20}=46499$ while $2^{20}=1048576$ for instance, so the bound is terrible. But you weren't asked to show a strong bound. – lulu Nov 06 '17 at 02:37
  • You have to start the induction off. Since you will need to go back three layers you will need to establish the claim for $t_1,t_2,t_3$. Happily, this is not difficult. – lulu Nov 06 '17 at 02:38
  • Why would I need to establish a claim for 1,2, and 3 if it's already stated in the recurrence? – user498021 Nov 06 '17 at 02:40
  • For completeness for the argument. Your argument and proof should be entirely self-contained (or at least as much as is reasonably possible). – JMoravitz Nov 06 '17 at 02:40
  • The recurrence never says explicitly that $t_1≤2^1,t_2≤2^2,t_3≤2^3$ . To be sure, all three follow effortlessly from what you are given but it still needs to be pointed out. – lulu Nov 06 '17 at 02:43
  • Ok, i'll state it. Thanks! – user498021 Nov 06 '17 at 02:43

0 Answers0