Corrected exercises: induction and recursion (201-N11)

Let $P(n)$ be a property depending on an integer $n$. If (1) BASE CASE: $P(n_{0})$ is true for a first rank $n_{0}$; and (2) INDUCTIVE STEP: for every $k\geq n_{0}$, $P(k)$ true implies $P(k+1)$ true; then $P(n)$ is true for every $n\geq n_{0}$. The inductive step is an implication, not an assertion: you never claim that $P(k)$ is true, you assume that it is.

BASE CASE at $n=1$: the left side equals 1, the right side $\frac{1\times 2}{2}=1$ ✓. INDUCTIVE STEP: assume $1+2+\dots+k=\frac{k(k+1)}{2}$ for some $k\geq 1$. Then $1+2+\dots+k+(k+1)=\frac{k(k+1)}{2}+(k+1)=(k+1)\left(\frac{k}{2}+1\right)=\frac{(k+1)(k+2)}{2}$, which is indeed the formula at rank $k+1$ ✓. Numerical check at $n=10$: $\frac{10\times 11}{2}=55$, and the sum is indeed 55.

Without a base case, the inductive step alone proves nothing. Take $P(n)$: “$n=n+1$”. The inductive step is PERFECTLY VALID: if $k=k+1$, then adding 1 to both sides gives $k+1=k+2$, that is, $P(k+1)$. The chain of implications is flawless, and yet $P(n)$ is false for every $n$, for lack of a first domino to push. This is the counterexample to remember, because it shows that a valid inductive step is worth nothing on its own.

Without an inductive step, checking cases proves nothing either. The property “$n^{2}+n+41$ is prime” is true for $n=0$, which gives 41, for $n=1$, which gives 43, and in fact for every integer from 0 to 39. It is FALSE at $n=40$, because $40^{2}+40+41=1681=41^{2}$. Forty successive checks are not worth a proof: the inductive step is what replaces infinitely many checks.

The initial push, the hand that knocks over the first domino, represents the BASE CASE. The chain, that is, the fact that each domino stands close enough to the next one to knock it over, represents the INDUCTIVE STEP. Without the push, the chain stays standing; without the chain, only the first domino falls. You need both, and the picture also says why: each of the two ingredients is useless without the other.

BASE CASE at $n=1$: on the left 1, on the right $\frac{1\times 2\times 3}{6}=1$ ✓. INDUCTIVE STEP: assuming the formula at rank $k$, the sum at rank $k+1$ equals $\frac{k(k+1)(2k+1)}{6}+(k+1)^{2}=\frac{(k+1)\left[k(2k+1)+6(k+1)\right]}{6}=\frac{(k+1)\left(2k^{2}+7k+6\right)}{6}=\frac{(k+1)(k+2)(2k+3)}{6}$, which is the formula at rank $k+1$ ✓. The decisive step is factoring $2k^{2}+7k+6$ as $(k+2)(2k+3)$: you find it by looking for the expected form, never by expanding at random. Check at $n=5$: $1+4+9+16+25=55$ and $\frac{5\times 6\times 11}{6}=55$ ✓.

Rank 5 is necessary: at $n=2$, $4>4$ is false; at $n=3$, $8>9$ is false; at $n=4$, $16>16$ is false. At $n=5$: $32>25$ ✓, the base case holds. INDUCTIVE STEP: assume $2^{k}>k^{2}$ with $k\geq 5$. Then $2^{k+1}=2\times 2^{k}>2k^{2}$. It remains to show that $2k^{2}\geq(k+1)^{2}$, that is, $k^{2}-2k-1\geq 0$, which is true as soon as $k\geq 3$ since $k^{2}-2k-1=(k-1)^{2}-2$. Hence $2^{k+1}>(k+1)^{2}$ ✓. An inequality proved by induction almost always needs this extra bounding step.

BASE CASE: $3^{2}-2=9-2=7$, divisible by 7 ✓. INDUCTIVE STEP: assume $3^{2k}-2^{k}=7m$ for an integer $m$. Then $3^{2(k+1)}-2^{k+1}=9\times 3^{2k}-2\times 2^{k}=9\left(3^{2k}-2^{k}\right)+9\times 2^{k}-2\times 2^{k}=9\times 7m+7\times 2^{k}=7\left(9m+2^{k}\right)$, a multiple of 7 ✓. The trick is to force the expression of rank $k$ to appear by adding and subtracting the missing term. Check at $n=3$: $729-8=721=7\times 103$ ✓.

SUM: the hypothesis replaces the sum of the first $k$ terms by its closed form, which turns a sum into an algebraic expression. INEQUALITY: the hypothesis supplies the lower bound $2^{k}>k^{2}$, which you multiply by 2. DIVISIBILITY: the hypothesis supplies the form $3^{2k}-2^{k}=7m$, which you factor out. In all three cases, it serves to REPLACE an expression of rank $k$ by something known.

Because if the hypothesis is never used, you have proved $P(k+1)$ directly, without assuming anything: induction was therefore not needed, and it is far more likely that a mistake was made, typically assuming what had to be proved. The check is worth doing every time: reread the inductive step and put your finger on the exact place where the hypothesis was used. If you cannot find one, something is wrong.

STRONG INDUCTION: if $P(n_{0})$ is true, and if for every $k$ the fact that $P(n_{0}),P(n_{0}+1),\dots,P(k)$ are ALL true implies $P(k+1)$, then $P(n)$ is true for every $n\geq n_{0}$. The difference lies in the hypothesis: you no longer have only rank $k$ but ALL the ranks up to $k$. The two principles are in fact logically equivalent, but the strong form is far more convenient as soon as you split an object into pieces of unknown sizes.

BASE CASE: 2 is prime, so it is its own prime divisor ✓. STRONG INDUCTIVE STEP: let $n\geq 3$, and assume the property true for all integers from 2 to $n-1$. Two cases. If $n$ is prime, it has $n$ as a prime divisor ✓. Otherwise, $n$ can be written $n=ab$ with $2\leq a<n$, and the strong hypothesis applied to $a$ gives a prime divisor $p$ of $a$; since $p$ divides $a$, which divides $n$, $p$ divides $n$ ✓. You can see why ordinary induction would not be enough: the factor $a$ has no reason to be equal to $n-1$.

You need TWO, at ranks 0 and 1. The reason is that the inductive step derives rank $n+2$ from ranks $n+1$ AND $n$: to get started, you must therefore have two consecutive values already established. With a single base case, you could never compute $F_{2}$, for lack of one of the two terms it depends on.

BASE CASES: $F_{0}=0<1=2^{0}$ ✓ and $F_{1}=1<2=2^{1}$ ✓. INDUCTIVE STEP: assume $F_{k}<2^{k}$ and $F_{k+1}<2^{k+1}$. Then $F_{k+2}=F_{k+1}+F_{k}<2^{k+1}+2^{k}=2^{k}\left(2+1\right)=3\times 2^{k}<4\times 2^{k}=2^{k+2}$ ✓. The final bound is generous, and that is deliberate: you prove what is asked, not the best possible result. Check: $F_{10}=55<1024=2^{10}$ ✓.

Yes, it fails. This sequence satisfies $u_{n}=2^{n+1}-1$: we have $u_{0}=1$, $u_{1}=3$, $u_{2}=3\times 3-2\times 1=7$, $u_{3}=3\times 7-2\times 3=15$. Suppose you want to prove “$u_{n}$ is odd” with a base case at rank 0 only. The inductive step $u_{n+2}=3u_{n+1}-2u_{n}$ needs $u_{n+1}$ AND $u_{n}$; at the step that produces $u_{2}$, you only have $u_{0}$, and the proof stops dead. This is not a fine point of write-up: the number of base cases must always equal the number of earlier ranks the relation depends on.

The recursive version is a literal translation of the definition $n!=n\times(n-1)!$ with $0!=1$. The iterative version accumulates the product in a loop. Both compute the same thing; the recursive one is closer to the mathematical definition, the iterative one uses constant memory. Check: $5!=120$ and $10!=3{,}628{,}800$ in both cases.

(1) There must be a BASE CASE, that is, at least one value for which the function answers without calling itself. (2) Every recursive call must be made on a STRICTLY SMALLER argument, one that eventually reaches the base case. Violating the first: a function written only as $f(n)=f(n-1)$ never stops. Violating the second: $f(n)=f(n)+1$, or more insidiously $f(n)=f(n-2)$ called on an odd number when the base case is $f(0)$, which always misses its target by one.

The naive version translates the relation $F_{n}=F_{n-1}+F_{n-2}$ with two base cases. It is correct but catastrophically slow, for the reason examined in exercise 5: it recomputes the same values over and over.

With a negative argument, the base case $n=0$ is never reached: the calls go down to $-1$, $-2$, and so on, without end. Python eventually raises a maximum recursion depth error. FIX: add a guard at the start of the function that rejects negative inputs, for example by raising an exception. This is exactly the illustration of the second condition of question b: the argument does decrease, but it never meets the base case.

The CALL STACK is the memory area where the interpreter keeps, for each call in progress, the local variables and the place to return to once the computation is finished. A recursion of depth $n$ stacks $n$ records there at the same time. By default Python sets a limit of about a thousand nested calls, not for lack of memory but as a SAFEGUARD: it turns an infinite recursion, which would crash the process in an opaque way, into a readable exception. You can raise this limit, but it is almost always a sign that a loop should have been written.

The tree has 15 nodes, so 15 calls in all. The value $\mathrm{fib}(2)$ appears in it THREE times, and $\mathrm{fib}(1)$ five times. These recomputations are not a programming flaw: they are built into the structure of the tree, where two branches coming out of the same node go down to subproblems that overlap.

A call to $\mathrm{fib}(n)$ counts for itself, plus all the calls of its two subtrees: $C(n)=1+C(n-1)+C(n-2)$ for $n\geq 2$, with $C(0)=C(1)=1$. Computations: $C(2)=1+1+1=3$; $C(3)=1+3+1=5$; $C(4)=1+5+3=9$; $C(5)=1+9+5=15$, which confirms the figure; $C(6)=1+15+9=25$.

By two-step induction. BASE CASES: $2F_{1}-1=2\times 1-1=1=C(0)$ ✓ and $2F_{2}-1=2\times 1-1=1=C(1)$ ✓. INDUCTIVE STEP: assuming the formula at ranks $k$ and $k+1$, we have $C(k+2)=1+C(k+1)+C(k)=1+\left(2F_{k+2}-1\right)+\left(2F_{k+1}-1\right)=2\left(F_{k+2}+F_{k+1}\right)-1=2F_{k+3}-1$ ✓. Check: $C(5)=2F_{6}-1=2\times 8-1=15$ ✓.

$C(30)=2F_{31}-1=2\times 1{,}346{,}269-1=2{,}692{,}537$ calls, that is, about 2.7 million. At a million calls per second, this takes about $2.7$ seconds for a computation whose result, $F_{30}=832{,}040$, fits in six digits. At $n=50$ it would take more than eleven hours, and at $n=80$ some 2,400 years: the growth is like $\varphi^{n}$, where $\varphi\approx 1.618$ is the golden ratio.

With memoization, each value $\mathrm{fib}(k)$ is computed only ONCE, for $k$ from 0 to $n$: the number of actual calls becomes linear, on the order of $2n+1$. For $n=30$, that makes 61 calls instead of 2.7 million, a gain by a factor of 44,000. The lesson goes beyond Fibonacci: as soon as the subproblems OVERLAP, storing the results turns an exponential cost into a linear cost. This is the principle of dynamic programming.

Substituting $u_{n}=r^{n}$ into the relation: $r^{n+2}=r^{n+1}+r^{n}$, and dividing by $r^{n}$, which is not zero, $r^{2}=r+1$, that is, $r^{2}-r-1=0$. The discriminant is $1+4=5$, so the two roots are $\varphi=\frac{1+\sqrt 5}{2}\approx 1.618034$ and $\psi=\frac{1-\sqrt 5}{2}\approx-0.618034$. This equation is called the characteristic equation of the recurrence.

Since the relation is LINEAR, every combination $u_{n}=A\varphi^{n}+B\psi^{n}$ still satisfies it, and one can show that there are no others. The two initial conditions fix $A$ and $B$: $F_{0}=0$ gives $A+B=0$, so $B=-A$; $F_{1}=1$ gives $A\varphi-A\psi=A\sqrt 5=1$, so $A=\frac{1}{\sqrt 5}$. Hence BINET'S FORMULA: $F_{n}=\frac{\varphi^{n}-\psi^{n}}{\sqrt 5}$. A remarkable fact: this expression full of square roots gives an integer for every $n$.

$\varphi^{10}\approx 122.9919$ and $\psi^{10}\approx 0.0081$, so $\frac{122.9919-0.0081}{2.2360680}\approx\frac{122.9837}{2.2360680}\approx 55.0000$ ✓, which is indeed $F_{10}=55$. Computing directly with the relation gives the same value, as it should.

The second term $\frac{\psi^{n}}{\sqrt 5}$ has absolute value $\frac{0.618034^{n}}{2.236}$, which is less than $\frac{1}{2}$ from $n=1$ on and goes to 0 very fast. The gap between $F_{n}$ and $\frac{\varphi^{n}}{\sqrt 5}$ is therefore always less than one half, which means exactly that $F_{n}$ is the nearest integer. Check at $n=10$: $\frac{122.9919}{2.2360680}\approx 55.0036$, whose nearest integer is indeed 55. This dominance of one root over the other also explains the growth like $\varphi^{n}$ observed in exercise 5.

Characteristic equation: $r^{2}=3r-2$, that is, $r^{2}-3r+2=0$, with roots $r=1$ and $r=2$. General form: $u_{n}=A\times 1^{n}+B\times 2^{n}=A+B2^{n}$. Initial conditions: $u_{0}=A+B=1$ and $u_{1}=A+2B=3$. Subtracting, $B=2$, then $A=-1$. Hence $u_{n}=2^{n+1}-1$. Check: $u_{0}=1$, $u_{1}=3$, $u_{2}=7$, $u_{3}=15$ ✓, which confirms the conjecture stated in exercise 3. The procedure is identical; only the roots change.

You compare the value you are looking for with the MIDDLE element. If they are equal, you are done. If it is smaller, you start again in the left half; otherwise in the right half. At each round, the search interval is divided by two, as the figure shows: 16 cells, then 8, then 4, then 2, then 1. The essential condition is that the array be SORTED; otherwise the comparison with the middle tells you nothing about the two halves.

$T(n)=T\left(\frac{n}{2}\right)+1$, with $T(1)=1$: one comparison with the middle, then the same problem on one half. Unrolling: $T(n)=1+1+\dots+1$ as many times as you can divide $n$ by 2 before reaching 1, that is, $\log_{2}n$ times. Hence $T(n)\approx\log_{2}n+1$, a LOGARITHMIC cost.

$\log_{2}\left(10^{6}\right)=\frac{6\ln 10}{\ln 2}\approx 19.93$, so 20 comparisons are enough. Linear search would need up to a million, that is, 50,000 times more. In other words, doubling the size of the array adds ONE comparison to binary search and a million to linear search: that is the difference in nature between logarithmic and linear.

Because its two subproblems are never both explored: you CHOOSE one and drop the other. The call tree of Fibonacci branches in two at every node, hence its exponential size; that of binary search is a simple PATH of length $\log_{2}n$. So it is not recursion that is expensive, it is branching with overlap.

The cost is $n\log_{2}n$. Tree argument: the call tree has $\log_{2}n$ levels, since the size is divided by two at each step down. At EACH level, merging handles $n$ elements in total, shared among the calls of that level: $n$ at the top, two times $\frac{n}{2}$ at the next level, four times $\frac{n}{4}$ after that, always $n$ in total. The overall cost is therefore the number of levels times the work per level, that is, $n\log_{2}n$. For a million elements, that is about 20 million operations, against $10^{12}$ for a selection sort: this is why all the sorts used in practice are recursive.

FALSE. The BASE CASE is missing, and without it the inductive step proves nothing. The property “$n=n+1$” has a perfectly valid inductive step, since $k=k+1$ implies $k+1=k+2$, and yet it is false at every rank. The inductive step sets up a chain of implications; something still has to set it off.

FALSE. A hundred checks are not worth a proof, and Euler's example shows it: $n^{2}+n+41$ is prime for $n$ from 0 to 39 and stops being prime at $n=40$, where you get $1681=41^{2}$. There are properties whose first counterexample is beyond a billion. The role of the inductive step is precisely to replace infinitely many checks, which no finite number of trials can do.

FALSE, and it is the most stubborn misunderstanding of the chapter. You do NOT assume that $P(k)$ is true: you prove the IMPLICATION “if $P(k)$ then $P(k+1)$”. An implication can be true while its hypothesis is false, so nothing has been asserted about $P(k)$. What you prove is a transmission mechanism; the base case, for its part, supplies a true starting point, and the two together give the conclusion.

FALSE. Recursion is not expensive in itself: it is BRANCHING WITH OVERLAP that is. Recursive binary search costs $\log_{2}n$ comparisons, exactly like its iterative version; recursive merge sort, in $n\log_{2}n$, beats every quadratic iterative sort. What makes naive $\mathrm{fib}$ disastrous is that it recomputes the same values, and memoization brings it down to a linear cost without taking away its recursion.

FALSE. The relation $F_{n+2}=F_{n+1}+F_{n}$ involves TWO earlier ranks, so TWO base cases are needed, at ranks 0 and 1. With only one, you cannot even compute $F_{2}$. General rule: the number of base cases must equal the number of earlier ranks the relation depends on.

RULES: you move one disk at a time, taking it from the top of a peg, and you never put a disk on a smaller one. STRATEGY: to move $n$ disks from A to C, first move the top $n-1$ disks from A to B, using C as the intermediate peg; then move the large disk from A to C, the only direct move; finally move the $n-1$ disks from B to C, using A. The base case is $n=1$, where you move the single disk (the code below stops one step earlier, at $n=0$, where there is nothing to move and the count is 0).

The strategy gives directly $H(n)=2H(n-1)+1$ with $H(1)=1$. Computations: $H(2)=3$; $H(3)=7$; $H(4)=15$, the case of the figure; $H(5)=31$. You recognize the sequence $2^{n}-1$, which the next question proves.

BASE CASE: $H(1)=1=2^{1}-1$ ✓. INDUCTIVE STEP: assume $H(k)=2^{k}-1$. Then $H(k+1)=2H(k)+1=2\left(2^{k}-1\right)+1=2^{k+1}-2+1=2^{k+1}-1$ ✓. The formula is therefore established for every $n\geq 1$. Notice that the proof follows exactly the structure of the algorithm: this is typical of recursive problems, the proof and the program look alike.

$H(64)=2^{64}-1=18{,}446{,}744{,}073{,}709{,}551{,}615$ moves. At one per second, that is about $5.85\times 10^{11}$ years, that is, nearly 585 billion years. For comparison, the age of the Universe is estimated at about 13.8 billion years: the monks of the legend would therefore need a time forty times longer. It is the best teaching argument there is against the idea that a faster computer solves everything.