1

I am confused on how to proceed on the Inductive step for this problem. (sorry in advance if my Latex is trash, im still learning) I.H: Assume that $P(2), P(3), ...... P(m)$ holds where $m \in \mathbb{N}$ I broke it down into two cases. case $1$: $m +1$ is even, case $2$: $m + 1$ is odd. case 1: By definition of $m + 1$ being even $m + 1 = 2 k_{1}$ ($k_{1} \in \mathbb{N}$ so $\frac{m+1}{2} = k_{1}$, and thus covered by I.H. so $2^{k} \leq m + 1 \leq 2^{k+1}$. However, I get stuck on the odd case as there can be composite odd numbers but those dont necessarily result in $2^{k-1} \leq m+1 \leq 2{k}$ form

user289143
  • 4,440
  • Does it have to be by induction? – lhf Oct 16 '19 at 23:37
  • well we are proving it for all n, for n >= 2 so I thought induction was the most intuitive idea, but if you have another idea by all means –  Oct 16 '19 at 23:40
  • $n\le 2^n.$ So let $k $ be the least $j$ such that $n\le 2^j.$ The well-order principle (applied to $\Bbb N$) is that if there exists $j\in \Bbb N$ with some property then there is a least such $j$. The well-order principle is equivalent to induction – DanielWainfleet Oct 17 '19 at 02:38
  • Im not familiar with the well ordered axiom. can you please explain it? –  Oct 17 '19 at 05:03

2 Answers2

1

Hint: The set $\{ m \in \mathbb N : 2^m \le n \}$ is finite and so has a maximal element, since it is not empty.

lhf
  • 216,483
1

Assume $P(m)$ so for some $k_0$ we have $2^{k_0-1}\leq m\leq 2^{k_0}$ then if $m+1\leq 2^{k_0}$ we are done since $2^{k_0-1}\leq m\leq m+1$ otherwise we had $m=2^{k_0}$ so $2^{k_0}\leq m+1\leq 2^{k_0}+1\leq 2^{k_0}+2^{k_0}=2^{k_0+1}$

kingW3
  • 13,496
  • where do you use the induction hypothesis? or can one not apply it in this situation? –  Oct 17 '19 at 01:13
  • @Curious_Mind I assumed that it works for $m$, that such $k$($k_0$) exists for $m$ and I proved that it exists for $m+1$ along with base case $n=2$ ($2^1\leq 2\leq 2^2$)this finishes the proof – kingW3 Oct 17 '19 at 01:33