Incomprehensible induction from Johnsonbaugh's book.

Question

How is this a proof by induction? If it is, aren't you supposed to be going from 4.3.3 to 4.3.4? This is an example from Johnsonbaugh's book.

EDIT: The question is: Find a theta notation in terms of n for the number of times the statement x = x + 1 is executed:

1. i = n
2. while (i ≥ 1) {
3. x = x + 1
4. i = Math.floor(i/2)
5. }

We were able to find the notation if n is a power of 2, easily achievable. However, in other cases, we can see that n is between 2 power of 2s. Thus the equation we see below. However, I'm failing to understand how the demo goes from 4.3.3 to 4.3.4. Why is he supposing 4.3.4? I think I'm misunderstanding a step in the explanation.

Answer 1

"How is this a proof by induction?" Honestly, I couldn't tell you. Maybe I'm just missing context, but that proof you posted looks absolutely horrendous. I don't even think it's correct. For one thing, it makes no sense to perform induction over the variable $k$ when we are trying to proof a statement for all of $n$. The best I can do to provide my own proof.

Statement: For every positive integer $n$ there exists some positive integer $k$ such that $$2^{k-1}\leq n < 2^k$$

Base Case:

The statement is clearly true for $n=1$ since for $k=1$ $$2^{1-1}=1\leq 1 < 2=2^1$$

Induction:

Now suppose for some positive integer $N$ we have for some $k$ $$2^{k-1}\leq N < 2^k$$

We need to show the statement holds for $N+1$. If $N+1<2^k$ $$2^{k-1}\leq N < N+1< 2^k$$

and we are done. Otherwise $N+1\geq 2^k$ and then $$2^k\leq N+1\leq N+N=2N<2*2^k=2^{k+1}$$

so in either case the statement holds for $N+1$.

Thus, by the principle of mathematical induction the statement holds for all positive integers $n$.