# A Proof by Strong Induction

I am having trouble approaching this question.

""''

t is defined as follows:

""''

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.

• Possible duplicate of math.stackexchange.com/questions/2506331/… – Math Lover Nov 6 '17 at 2:30
• Strong induction is a natural approach, and works very easily. – quasi Nov 6 '17 at 2: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 6 '17 at 2:31
• Another duplicate question (albeit one that has not received a full answer, but plenty of guidance in the comments). – JMoravitz Nov 6 '17 at 2:33
• @quasi The fact that you conclude this suggets that you are really smart. ;-) – amsmath Nov 6 '17 at 2:38

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}$.
• @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 6 '17 at 3: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 6 '17 at 3:35