Homework-2, Adaptation course in DM-2022, Induction principle
To facilitate the discovery of proofs,
it is important to be familiar with some standard styles of arguments.
Induction is one such style.

In our classes we agreed to use the following steps for the proofs with induction:

0. Define  the statement P(n) you want to prove for all n ≥ 0 .

1. Base case: Prove that P(0) is true. You do this directly.

2. Inductive step: Prove that P(k) → P(k + 1) for all k ≥ 0. That is, prove that for any k ≥ 0 if P(k) is true, then P(k + 1) is true
as well.

Assuming you are successful on both parts above, you can
conclude,  “Therefore by the principle of mathematical induction, the statement P(n) is true for all n ≥ 0.”

Put your answers after the questions or send them to me directly @AnastasiiaTrofimova
Sign in to Google to save your progress. Learn more
My name is
 *
1 point
1. Explain the error made in the following proof by induction. Is base case, inductive step or, maybe, the proof itself.

(First wrong reasoning)

Let us prove by induction that any two neighboring
natural numbers are equal. In other words, we want to prove the statement A(n)  = " n = n+1".

We will prove by assumption that it is true for all smaller values ​​of n. Then it must also be true for the previous value of the parameter n . It
means that (𝑛 − 1) = (𝑛 − 1) + 1, i.e. 𝑛 − 1 = 𝑛 . Adding one
to both sides of the equality, we get that 𝑛 = 𝑛 + 1.
Therefore by the principle of mathematical induction, the statement P(n) is true for all n ≥ 0. *
1 point
2. Explain the error made in the following proof by induction. Is base case, inductive step or, maybe, the proof itself.

(Second wrong reasoning) Let us prove that any n numbers are equal P(n): if a_1, ..., a_n
arbitrary numbers, then 𝑎1 = 𝑎2 = . . . = 𝑎𝑛 .

With 𝑛 = 1, there is nothing to prove: there is only one number and it is equal to itself
yourself. Let us now prove that any n numbers are equal by assuming (as usual)
but is done by reasoning by induction), which for smaller n is already
known. Consider arbitrary numbers a_1, ....a_{n-1}, a_n. Excluding the last number, we get a set of n-1 numbers. By the induction hypothesis, they
are equal:
a_1 = a_2 = ...= a_{n-1}.
Now let's drop the first number. Again we get a set of n-1 numbers, and
the induction hypothesis gives
a_2 =a_3 =  ...a_{n}.
Combining these two equalities, we get that
a_1 = a_2 = ... = a_n.
 *
1 point
3. For Fibonacci sequence {F_n}
F_0 = 0, F_1 = 1, F_{N+1} = F_n + F_{n-1}
prove that F_0 + F_2 + F_4 + · · · + F_2n  =  F_{2n+1} − 1. *
1 point
4. Prove that 7^n − 1 is a multiple of 6 for all natural n. *
1 point
5. Prove, using strong induction, that every natural number is either a
Fibonacci number or can be written as the sum of distinct Fibonacci
numbers. *
1 point
6. The businessman made such a deal with the devil: he can exchange the banknote he has with the devil for any set of banknotes of any lesser denomination (of your choice, without limiting the total amount). He can also spend money, but he cannot receive it elsewhere. (except for the devil). Moreover, every day he needs a ruble for food. Will be able does he live like this indefinitely? *
1 point
Submit
Clear form
Never submit passwords through Google Forms.
This content is neither created nor endorsed by Google. Report Abuse - Terms of Service - Privacy Policy
Google Forms