DT6248 Discrete Maths proofs and Mathematical Induction Homework Solutions.
1)Prove that for all integers m and n, if m and n are odd, then mn is odd.
Answers: Let m and n be odd integers. Then there exist k1 and k2 such that m = 2k1 + 1 and n = 2k2 +1. Now mn = (2k1 + 1) (2k2 +1) = 4k1k2 +2k1 +2k2 + 1 = 2(2k1k2 + k1 +k2) +1. Therefore, mn is odd.
2)Show, by giving a proof by contradiction, that if 40 coins are distributed among nine bags so that each bag contains at least one coin, at least two bags contain the same number of coins.
Answers: Suppose that the conclusion is false, that is, that no two bags contains the same number of coins. Suppose that we rearrange the bags in increasing order of the number of coins that they contain. Then the first bag contains at least one coin; the second bag contains at least two coins, and so on. Thus, the total number of coins is at least 1 + 2 +3 + …..+ 9 = 45. This contradicts the hypothesis that there are 40 coins. The proof by contradiction is complete.
3)Use proof by contradiction to show that is not rational.
Answer:
Suppose is rational, i.e. where m and n are integers in lowest terms (no common factors).
4)Use proof by contradiction to show that real numbers , then either
Answer:
Assume neither
Therefore, if , then either
5)
Using induction, verify that each equation is true for every positive integer n.
a)1 + 3 + 5 + ….+ (2n – 1) = n2
Answers:
b)
Answers:
6)Use the geometric sum to prove that
for all
Answers:
7)Use induction to prove that 7n – 1 is divisible by 6 , for all
Answers:
8)Prove that the sum of the squares of the first positive integers is
Answer:
For
Assume true for ie (
Prove true for :
Show
9)Prove that, for all positive integers is divisible by 13.
Answer:
Assume true for
Prove true for
Which is clearly divisible by 13.
Page 1 of 4