Lesson test: Induction

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Induction

1.[1p]
To prove $P (n)$ for every natural number $n$ by induction, what must the inductive step establish?

For an arbitrary natural number $n$ , if $P (n)$ is true then $P (n + 1)$ is true

Correct

$P (n)$ is true for an arbitrary natural number $n$

The answer is: For an arbitrary natural number $n$ , if $P (n)$ is true then $P (n + 1)$ is true

$P (n + 1)$ is true for some natural number $n$

The answer is: For an arbitrary natural number $n$ , if $P (n)$ is true then $P (n + 1)$ is true

If $P (n + 1)$ is true then $P (n)$ is true, for every natural number $n$

The answer is: For an arbitrary natural number $n$ , if $P (n)$ is true then $P (n + 1)$ is true

2.[1p]
For the statement " $n^{2} + n$ is odd", the inductive step $P (n) \Rightarrow P (n + 1)$ can be proved, so the statement is true for every natural number $n$ .

True

The answer is: False

False

Correct

3.[2p]
The proof that induction is valid takes $m$ , the least natural number for which $P (m)$ fails. Why can $m$ not be $1$ ?

Because the base case says $P (1)$ is true

Correct

Because the inductive step says $P (1)$ implies $P (2)$

The answer is: Because the base case says $P (1)$ is true

Because $1$ has no predecessor in $ℕ$

The answer is: Because the base case says $P (1)$ is true

Because the well-ordering principle says the least element is at least $2$

The answer is: Because the base case says $P (1)$ is true

4.[1p]
What is the smallest natural number $n_{0}$ such that $2^{n} > n^{2}$ for every $n \geq n_{0}$ ?

CorrectNot quite: 5

5.[1p]
Use the formula $1^{2} + 2^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6}$ to find $1^{2} + 2^{2} + \dots + 20^{2}$ .

CorrectNot quite: 2870

6.[2p]
Put the lines of the proof that $6 ∣ n^{3} + 5 n$ for every natural number $n$ in order.

Expanding, $(n + 1)^{3} + 5 (n + 1) = (n^{3} + 5 n) + 3 (n^{2} + n) + 6$ .
So $(n + 1)^{3} + 5 (n + 1) = 6 k + 6 m + 6 = 6 (k + m + 1)$ .
For the base case, $1^{3} + 5 \times 1 = 6$ , which is a multiple of $6$ .
The middle term is a multiple of $6$ , since $n^{2} + n$ is even, so $n^{2} + n = 2 m$ for some integer $m$ .
By induction, $6 ∣ n^{3} + 5 n$ for every natural number $n$ .
For the step, assume $n^{3} + 5 n = 6 k$ for some integer $k$ .

Show the answer

a, b, c, d, e, f

7.[3p]
Match each claim to the base case its induction needs.

$1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ for every natural number $n$
$2^{n} > n^{2}$ for every $n \geq 5$
Every integer $n \geq 2$ is a product of primes
$F_{n} < 2^{n}$ for the Fibonacci numbers

$n = 5$ only
$n = 1$ only
both $n = 1$ and $n = 2$
$n = 2$ only

Show the answer

$1 + 2 + \dots + n = \frac{n (n + 1)}{2}$ for every natural number $n$ : $n = 1$ only $2^{n} > n^{2}$ for every $n \geq 5$ : $n = 5$ only Every integer $n \geq 2$ is a product of primes: $n = 2$ only $F_{n} < 2^{n}$ for the Fibonacci numbers: both $n = 1$ and $n = 2$

8.[3p]
Which of these are true of strong induction?

Select all that apply

The step may assume $P (k)$ for every $k$ from the base case up to $n$

Correct

It proves nothing that ordinary induction cannot, applied to " $P (1)$ through $P (n)$ all hold"

Correct

It is what the proof that every $n \geq 2$ is a product of primes needs, since $n + 1 = a b$ calls on $a$ and $b$

Correct

It needs no base case, because the step already assumes every earlier case

The answer is: The step may assume $P (k)$ for every $k$ from the base case up to $n$ , It proves nothing that ordinary induction cannot, applied to " $P (1)$ through $P (n)$ all hold", It is what the proof that every $n \geq 2$ is a product of primes needs, since $n + 1 = a b$ calls on $a$ and $b$

It also proves that the factorisation into primes is unique

9.[2p]
The "proof" that all horses are one colour has a true base case. Where exactly does it fail?

In the step from $n = 1$ to $n = 2$ : the two groups of one horse do not overlap

Correct

In the base case: one horse need not be one colour

The answer is: In the step from $n = 1$ to $n = 2$ : the two groups of one horse do not overlap

In the step for large $n$ , where the groups are too big to compare

The answer is: In the step from $n = 1$ to $n = 2$ : the two groups of one horse do not overlap

In every step, since removing a horse changes the colour of the group

The answer is: In the step from $n = 1$ to $n = 2$ : the two groups of one horse do not overlap

10.[1p]
Use the identity $F_{1} + F_{2} + \dots + F_{n} = F_{n + 2} - 1$ to find $F_{1} + F_{2} + \dots + F_{10}$ , where $F_{1} = F_{2} = 1$ and $F_{n + 2} = F_{n + 1} + F_{n}$ .

CorrectNot quite: 143

11.[1p]
What is the largest whole number of pence that cannot be paid exactly with 3p and 5p stamps?

CorrectNot quite: 7

12.[2p]
A direct induction on " $\sum_{k = 1}^{n} \frac{1}{k^{2}} < 2$ " fails, while one on " $\sum_{k = 1}^{n} \frac{1}{k^{2}} \leq 2 - \frac{1}{n}$ " succeeds. Why?

The stronger statement is also a stronger inductive hypothesis: it says how much room is left below $2$ , which the step needs

Correct

The weaker statement is false for large $n$

The answer is: The stronger statement is also a stronger inductive hypothesis: it says how much room is left below $2$ , which the step needs

The stronger statement has an easier base case

The answer is: The stronger statement is also a stronger inductive hypothesis: it says how much room is left below $2$ , which the step needs

Induction can only prove statements with $\leq$ , not $<$

The answer is: The stronger statement is also a stronger inductive hypothesis: it says how much room is left below $2$ , which the step needs

13.[1p]
Every non-empty set of non-negative rational numbers has a least element.

True

The answer is: False

False

Correct

14.[2p]
To prove by structural induction that every propositional formula built from variables with $\neg$ , $\land$ and $\lor$ has some property, what must be shown?

Every variable has the property, and if $φ$ and $ψ$ have it then so do $\neg φ$ , $(φ \land ψ)$ and $(φ \lor ψ)$

Correct

Every variable has the property, and nothing else needs checking

The answer is: Every variable has the property, and if $φ$ and $ψ$ have it then so do $\neg φ$ , $(φ \land ψ)$ and $(φ \lor ψ)$

If $φ$ and $ψ$ have the property then so do $\neg φ$ , $(φ \land ψ)$ and $(φ \lor ψ)$ , with no base case

The answer is: Every variable has the property, and if $φ$ and $ψ$ have it then so do $\neg φ$ , $(φ \land ψ)$ and $(φ \lor ψ)$

The property holds for every formula with at most three symbols

The answer is: Every variable has the property, and if $φ$ and $ψ$ have it then so do $\neg φ$ , $(φ \land ψ)$ and $(φ \lor ψ)$

1.[1p] To prove P(n) for every natural number n by induction, what must the inductive step establish?

2.[1p] For the statement "n2+n is odd", the inductive step P(n)⇒P(n+1) can be proved, so the statement is true for every natural number n.

3.[2p] The proof that induction is valid takes m, the least natural number for which P(m) fails. Why can m not be 1?

4.[1p] What is the smallest natural number n0 such that 2n>n2 for every n≥n0?

5.[1p] Use the formula 12+22+⋯+n2=n(n+1)(2n+1)6 to find 12+22+⋯+202.

6.[2p] Put the lines of the proof that 6∣n3+5n for every natural number n in order.

7.[3p] Match each claim to the base case its induction needs.

8.[3p] Which of these are true of strong induction?

9.[2p] The "proof" that all horses are one colour has a true base case. Where exactly does it fail?

10.[1p] Use the identity F1+F2+⋯+Fn=Fn+2−1 to find F1+F2+⋯+F10, where F1=F2=1 and Fn+2=Fn+1+Fn.

11.[1p] What is the largest whole number of pence that cannot be paid exactly with 3p and 5p stamps?

12.[2p] A direct induction on "∑k=1n1k2<2" fails, while one on "∑k=1n1k2≤2−1n" succeeds. Why?

13.[1p] Every non-empty set of non-negative rational numbers has a least element.

14.[2p] To prove by structural induction that every propositional formula built from variables with ¬, ∧ and ∨ has some property, what must be shown?

1.[1p]
To prove $P (n)$ for every natural number $n$ by induction, what must the inductive step establish?

2.[1p]
For the statement " $n^{2} + n$ is odd", the inductive step $P (n) \Rightarrow P (n + 1)$ can be proved, so the statement is true for every natural number $n$ .

3.[2p]
The proof that induction is valid takes $m$ , the least natural number for which $P (m)$ fails. Why can $m$ not be $1$ ?

4.[1p]
What is the smallest natural number $n_{0}$ such that $2^{n} > n^{2}$ for every $n \geq n_{0}$ ?

5.[1p]
Use the formula $1^{2} + 2^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6}$ to find $1^{2} + 2^{2} + \dots + 20^{2}$ .

6.[2p]
Put the lines of the proof that $6 ∣ n^{3} + 5 n$ for every natural number $n$ in order.

7.[3p]
Match each claim to the base case its induction needs.

8.[3p]
Which of these are true of strong induction?

9.[2p]
The "proof" that all horses are one colour has a true base case. Where exactly does it fail?

10.[1p]
Use the identity $F_{1} + F_{2} + \dots + F_{n} = F_{n + 2} - 1$ to find $F_{1} + F_{2} + \dots + F_{10}$ , where $F_{1} = F_{2} = 1$ and $F_{n + 2} = F_{n + 1} + F_{n}$ .

11.[1p]
What is the largest whole number of pence that cannot be paid exactly with 3p and 5p stamps?

12.[2p]
A direct induction on " $\sum_{k = 1}^{n} \frac{1}{k^{2}} < 2$ " fails, while one on " $\sum_{k = 1}^{n} \frac{1}{k^{2}} \leq 2 - \frac{1}{n}$ " succeeds. Why?

13.[1p]
Every non-empty set of non-negative rational numbers has a least element.

14.[2p]
To prove by structural induction that every propositional formula built from variables with $\neg$ , $\land$ and $\lor$ has some property, what must be shown?