Solving Recurrences
The First Example: Knuth Number (KN)
The first example: Knuth Number (KN)
We have the following example:
Prove or disprove that for \(n \geq 0\), \(K_n \geq n\).
- List small values for \(k\).
- Proof by induction.
- Base case: \(K=0\) satisfies the condition.
- Induction
KN: Induction Step
- Assume the inequality holds for all values up to some non-negative value \(n\),
- Goal: show that \(K_{n+1} \geq n+1\).
- Given \(K_{n+1}=1+\min(2K_{\lfloor{n/2}\rfloor}, 3K_{\lfloor{n/3}\rfloor})\), and \(2K_{\lfloor{n/2}\rfloor} \geq 2 \lfloor{n/2}\rfloor\), \(3K_{\lfloor{n/3}\rfloor}\geq 3\lfloor{n/3}\rfloor\) (by hypothesis),
- But \(2 \lfloor{n/2}\rfloor \) can be as small as \(n-1\), \(3\lfloor{n/3}\rfloor\) can be as small as \(n-2\), breaking the induction.
- Or really? This case jumps fast.
KN: The Special Case
We can prove by contradiction:
- Assume we can find a value \(m\) such that \(K_m \leq m\)
- Finding \(m\)'s origin, say \(m=n'+1\)
- Requires \(K_{\lfloor{n'/2}\rfloor}\leq \lfloor{n'/2}\rfloor\), and \(K_{\lfloor{n'/3}\rfloor}\leq \lfloor{n'/3}\rfloor\).
- This implies \(K_0 \leq 0\), but \(K_0 = 1\), contradiction.
About Mathematical Induction
In trying to devise a proof by mathematical induction, you may fail for two opposite reasons. You may fail because you try to prove too much: Your \(P(n)\) is too heavy a burden. Yet you may also fail because you try to prove too little: Your \(P(n)\) is too weak a support. In general, you have to balance the statement of your theorem so that the support is just enough for the burden."
Josephus Problem Generalized (JPG)
Idea: Whenever a person is passed over, give it a new number.
Demonstrate:
- What will the ID become?
- 1, 2 become \(n+1, n+2\)
- 3 executed;
- 4, 5 become \(n+3, n+4\);
- 6 is executed;
- \(3k+1, 3k+2\) will become \(n+2k+1, n+2k+2\);
-
\(3k+3\) is executed.
-
Counting is consistent, no jumping over someone.
- The \(k\)-th person eliminated ends up with number \(3k\).
-
To find the survivor = figure out the original number \(3N\).
-
What is \(3N\) originally?
- \(N(N>n)\) has a form of \(N = n+2k+1\) or \(N=n+2k +2\), in a single round.
- for two \(k\)s, getting \(k_1 = (N-1-n)/2\), \(k_2=(N-2-n)/2\).
- \(=\lfloor(N-n-1)/2\rfloor\).
An algorithm for this: - Let \(N \leftarrow 3n\); - while \(N>n\), let \(N\leftarrow \lfloor(N-n-1)/2\rfloor+N-n\); - Answer\(\leftarrow N\).
Simplifying this algorithm: like treating arithmetic series: - Assign the numbers from largest to smallest - yielding \(\lceil 3/2D \rceil\).
Generalized: \(D=\lceil q/(q-1)D \rceil\) for general \(q\)s, i.e., \(q\)-kill one.