05 Induction and Recursion Free Online FlashCards

What are the two parts of ordinary mathematical induction?

Mathematical induction requires a true base case and a proof that, for every relevant $k$, $P(k)\Rightarrow P(k+1)$.

What is the induction hypothesis?

The induction hypothesis is the assumption that $P(k)$ is true for an arbitrary $k$ in the induction range.

What formula gives the sum $1+2+\cdots+n$?

For every $n\geq 1$, $1+2+\cdots+n=\frac{n(n+1)}{2}$.

Why is assuming $P(k+1)$ a circular induction error?

A circular error is assuming $P(k+1)$ when trying to prove $P(k+1)$; ordinary induction permits assuming only $P(k)$.

What additional assumption does strong induction provide?

Strong induction permits assuming all earlier statements $P(n_0),P(n_0+1),\ldots,P(k)$ when proving $P(k+1)$.

When is strong induction especially useful?

Strong induction is useful when the case of size $k+1$ depends on several smaller cases, not necessarily only the case of size $k$.

What property of integers greater than 1 is proved by strong induction?

Every integer greater than 1 is either prime or has a prime factor.

State the well-ordering principle.

Every nonempty subset of the nonnegative integers has a least element.

How does the least-counterexample method work?

Choose the least counterexample, then use the truth of every smaller case to prove the statement for it, creating a contradiction.

What three components normally form a recursive definition?

A recursive definition has base clause(s), recursive clause(s), and a closure condition restricting the collection to objects generated by those clauses.

What is the recursive definition of factorial?

The factorial recursion is $0!=1$ and $(n+1)!=(n+1)n!$ for $n\geq 0$.

What recurrence defines the Fibonacci sequence?

The Fibonacci sequence uses $F_0=0$, $F_1=1$, and $F_n=F_{n-1}+F_{n-2}$ for $n\geq 2$.