CmSc 180 – Discrete Mathematics
Homework 08: Solution
1. Suppose you know from previous experience that every card has a letter on one side and a number on the other side. You are given the rule, “If a card has a vowel on one side, then it has an even number on the other side.” Which cards do you need to turn over in order to find out whether this rule is true or false?
Cards:
1) A
2) C
3) 4
4) 9
To prove that a rule P ® Q is true we need to show that whenever P is true, Q is also true, and that whenever Q is false, P is also false.
The rule above can be stated as:
vowel ® even number (1)
And
not even number ® not vowel (2)
Card (1) matches the left side of (1) , so we need to turn it over.
Card (4) matches the left side of (2) so we need to turn it over.
Cards (2) and (3) do not match rules (1) and (2), so we don’t need to turn them over.
2. Find the first four terms of each of the following sequences defined by an explicit formula:
a. an = n/(n+1)2, n = 1, 2, 3, …. 1/4, 2/9, 3/16, 4/25, …
b. an = (-1)n+1 n/(n+1), n = 1, 2, 3, . .. 1/2, -2/3, 3/4, -4/5, …
c. an = (-2)n-1 /n, n = 1, 2, 3, . .. 1, -1, 4/3, -8/4, …
3. Find the first four terms of each of the following recursively defined sequences
a. ak+1 = 4ak, k = 0, 1, 2, …. 1, 4, 16, 64, 256, …
a0 = 1
b. ak = k(ak-1)2, k = 1, 2, 3, 4, 5, .. 2, 4, 32, 3072, 37748736,…
a0 = 2
4. Find explicit formulas for the following sequences:
a. 1 - 1/2, 1/2 - 1/3, 1/3 - 1/4, 1/4 - 1/5, ….
an = 1/n – 1/(n+1),, n = 1, 2, 3,….
b. 1/4, 2/9, 3/16, 4/25, 5/36, 6/69, …
an = n/(n+1)2, n = 1, 2, 3,….
c. 1/2, -2/3, 3/4, -4/5, 5/6, -6/7, ….
an = (-1)(n-1) n/(n+1), n = 1, 2, 3,….
d. 2, 6, 12, 20, 30, 42, 56, ….
an = n.(n+1), n = 1, 2, 3,….
5. The following sequence is given by a recursive rule. Make a hypothesis about its explicit formula and prove your hypotheses using mathematical induction
ak+1 = ak + 2(k+1), k =1, 2, 3, 4, 5, ..
a1 = 1
Terms: 1, 5, 11, 19, 29, 41, …
Hypothesis: an = n.(n+1) - 1
Proof:
1. Inductive base: P(1): a1 = 1.(1+1) - 1
By definition of the sequence a1 = 1
Therefore P(1) is true
2. Inductive step
Assume that P(k): ak = k.(k+1) – 1 is true
We will show that P(k+1): ak+1 = (k+1).(k+2) – 1 is also true
By the recursive definition of the sequence we have:
ak+1 = ak + 2(k+1) (1)
By the assumption ak = k.(k+1) – 1
Substituting in (1) we obtain:
ak+1 = ak + 2(k+1) = k.(k+1) – 1+ 2(k+1) =
= (k+1)(k+2) -1
Therefore P(k+1) is also true.
By the principle of mathematical induction P(n) is true for any n ³ 1
6. Prove by mathematical induction that for all n ³ 1,
1/ (1.2) + 1/(2.3) + 1/(3.4) + .. + 1/(n(n+1)) = n/(n+1)
Consider the sequence of sums:
S1 = 1/(1.2)
S2 = 1/(1.2) + 1/(2.3)
S3 = 1/(1.2) + 1/(2.3) + 1/(3.4)
…
We want to show that Sn = n /(n+1)
The sequence S1, S2, …. can be defined recursively :
S1 = 1/2
Sn = Sn-1 + 1/n(n+1)
We will prove that P(n): Sn = n/(n+1) is true for any n ³ 1
1. Inductive base
We want to show that P(1): S1 = 1/2 is true
By the definition of the sequence S1 = 1/(1.2) = 1/2
Therefore P(1) is true
2. Inductive step
Assume that P(k): Sk = k/(k+1) is true (1)
We will show that under this assumption
P(k+1): Sk+1 =(k + 1)/(k+2) is also true (2)
By the recursive definition
Sk+1 = Sk + 1/(k+1)(k+2) (3)
Substituting Sk in (3) with its expression from (1) we obtain:
Sk+1 = k/(k+1) + 1/(k+1)(k+2) =
k(k+2)/(k+1)(k+2) + 1/(k+1)(k+2) =
(k(k+2) + 1) /(k+1)(k+2) =
( k2 + 2k + 1) /(k+1)(k+2) =
(k+1)(k+1) /(k+1)(k+2) =
(k+1)/(k+2)
Therefore (2) is true.
Therefore by the principle of mathematical induction
Sn = n/(n+1) for any n ³ 1
2