0
$\begingroup$

I am having trouble approaching this question.

""''

t is defined as follows:

Definition of t

""''

I want to prove that last statement in the image.

I have been thinking about proving by strong induction. However, I am also confused about how many (minimum amount of) base cases do I need to take. Any suggestions and guidance is appreciated.

Note: If you think there is a simpler way to prove this without using strong induction, then kindly shed light on that.

$\endgroup$
6
  • $\begingroup$ Possible duplicate of math.stackexchange.com/questions/2506331/… $\endgroup$ – Math Lover Nov 6 '17 at 2:30
  • $\begingroup$ Strong induction is a natural approach, and works very easily. $\endgroup$ – quasi Nov 6 '17 at 2:30
  • $\begingroup$ Strong induction in this case can simply be rephrased as straightforward induction by letting the statement be $P(k)$ is true iff each of the following three inequalities are true: $t_k<2^k,t_{k-1}<2^{k-1},t_{k-2}<2^{k-2}$. There is little reason to make the change however, as wording the proof using strong induction should not cause any additional difficulty or discomfort. $\endgroup$ – JMoravitz Nov 6 '17 at 2:31
  • $\begingroup$ Another duplicate question (albeit one that has not received a full answer, but plenty of guidance in the comments). $\endgroup$ – JMoravitz Nov 6 '17 at 2:33
  • 1
    $\begingroup$ @quasi The fact that you conclude this suggets that you are really smart. ;-) $\endgroup$ – amsmath Nov 6 '17 at 2:38
3
$\begingroup$

Base case: $t_1 = 1 < 2^1 = 2$, $t_2 = 1 < 2^2 = 4$, $t_3 = 1 < 2^3 = 8$.

Assume there is some $k\geq 3$ such that $t_i < 2^i$ for all $ i \leq k$.

$t_k < 2^k$, $t_{k-1} < 2^{k-1}$, and $t_{k-2} < 2^{k-2}$. Then from here show that somehow $t_{k+1} < 2^{k+1}$.

$\endgroup$
3
  • $\begingroup$ Could you please explain why do you say " k≥3 " instead of just " k>3 ", since we already have shown the third base case to be true? And also why " i ≤ k " ? Should it not be just i<k ? I am so confused as to what my Inductive Hypothesis should be..... please help. I'm going crazy $\endgroup$ – AI_Bush Nov 6 '17 at 3:30
  • $\begingroup$ @AI_Bush Well the way that induction works is that you are assuming that for at least one $k$, your proposition holds. If you say $k>3$, then you can't say that. That's what the base case is for, it's to show that the proposition holds at least once, and the induction later builds off of that. $\endgroup$ – ultrainstinct Nov 6 '17 at 3:33
  • $\begingroup$ @AI_Bush Now strong induction you're assuming that for at least one $k$ we have that the proposition holds for all $i \leq k$. $\endgroup$ – ultrainstinct Nov 6 '17 at 3: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.