Discrete Mathematics

What is the induction hypothesis assumption for the inequality $m! > 2^m$ where $m \ge 4$?

(i) For $m=k$, $k+1! > 2^k$ holds
(ii) For $m=k$, $k! > 2^k$ holds
(iii) For $m=k$, $k! > 3^k$ holds
(iv) For $m=k$, $k! > 2^{k+1}$ holds

Find the greatest common divisor of 414 and 662 using the Euclidean algorithm.

If $a$ and $b$ are positive integers, then prove that there exists integers $s$ and $t$ such that $\text{gcd}(a, b) = sa + tb$.

Prove the following by using the principle of mathematical induction for all $n \in N$:
$$1^3 + 2^3 + 3^3 + \dots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$$

Use mathematical induction to prove this formula for the sum of a finite number of terms of a geometric progression with initial term $a$ and common ratio $r$:
$$\sum_{j=0}^{n} ar^j = a + ar + ar^2 + \dots + ar^n = \frac{ar^{n+1} - a}{r-1}$$
when $r
e 1$where$n$ is a non-negative integer.

State and prove Division algorithm theorem well-ordering principle.

An odd number of people stand in a yard at mutually distinct distances. At the same time each person throws a pie at their nearest neighbour, hitting this person. Use mathematical induction to show that there is at least one survivor, that is, at least one person who is not hit by a pie.

Prove Bernoulli's inequality that if $h > -1$, then $1+nh \le (1+h)^n$ for all non-negative integers $n$.

What is pigeonhole principle? Using it, prove the following:

(a) During a month with 30 days, a baseball team plays at least one game a day, but no more than 45 games. Show that there must be a period of some number of consecutive days during which the team must play exactly 14 games.

A grocery store employee is stocking apples. Each apple is a different color. There are 10 apples left

in the box and the employee pulls out 2 of them at random. What is the probability that the employee

pulls out one pink apple and yellow apple?

The sequence $8, 11, 9, 1, 4, 6, 12, 10, 5, 7$ contains 10 terms. Note that $10 = 3^2 + 1$. There are four strictly increasing subsequences of length four, namely, $1, 4, 6, 12$; $1, 4, 6, 7$; $1, 4, 6, 10$; and $1, 4, 5, 7$. There is also a strictly decreasing subsequence of length four, namely, $11, 9, 6, 5$.