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 \ge 2$ is a product of primes needs, since $n + 1 = ab$ 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

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?

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?