0

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.

AI_Bush
  • 57
  • Possible duplicate of https://math.stackexchange.com/questions/2506331/2x-1-2x-2-2x-3-2x#comment5176373_2506331 – Math Lover Nov 06 '17 at 02:30
  • Strong induction is a natural approach, and works very easily. – quasi Nov 06 '17 at 02:30
  • 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. – JMoravitz Nov 06 '17 at 02:31
  • Another duplicate question (albeit one that has not received a full answer, but plenty of guidance in the comments). – JMoravitz Nov 06 '17 at 02:33
  • The fact that the question is an exact duplicate (i.e., the image is the same) suggests two students from the same class. – quasi Nov 06 '17 at 02:33
  • 1
    @quasi The fact that you conclude this suggets that you are really smart. ;-) – amsmath Nov 06 '17 at 02:38

1 Answers1

3

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}$.

ultrainstinct
  • 2,651
  • 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 – AI_Bush Nov 06 '17 at 03:30
  • @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. – ultrainstinct Nov 06 '17 at 03:33
  • @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$. – ultrainstinct Nov 06 '17 at 03:35