Prove by induction : if n < =(2^k) -1 then we can find the number with k guesses
To prove this statement by induction, we need to show that it holds true for a base case and then prove the inductive step.
Base Case:
Let's start by proving the statement for the base case, which is when n = 1. In this case, k = 1 since (2^k) - 1 equals 1. If there is only one number to guess, we can find it in just one guess. Therefore, the statement is true for the base case.
Inductive Step:
Now, let's assume that the statement holds true for some arbitrary positive integer, m. That is, if m ≤ (2^k) - 1, then we can find the number within k guesses.
We want to prove that the statement also holds true for m + 1. That is, if (m + 1) ≤ (2^k) - 1, then we can find the number within k guesses.
Now, we can make an additional guess by dividing the search space into two equal halves. If the target number is in the first half, we continue our search in that half. Otherwise, it must be in the second half.
In the worst-case scenario, the target number is in the second half, which contains (2^(k-1)) - 1 elements. Since m + 1 ≤ (2^k) - 1, we have m ≤ (2^(k-1)) - 1. By our assumption, we can find m in k-1 guesses. Therefore, we can find m + 1 in at most k-1 additional guesses.
Therefore, it is possible to find (m + 1) ≤ (2^k) - 1 within k guesses.
By the principle of induction, we conclude that for any positive integer n ≤ (2^k) - 1, we can find the number with k guesses.