1. Use induction to prove: 2+4+6+···+2n=n(n+1) 2. Examine the following Relation

Question

1. Use induction to prove:
2+4+6+···+2n=n(n+1)

2. Examine the following Relations:
a.   x y
b.   Set inclusion on a collection C of sets.
Are relations (a) and (b)reflexive, symmetrical, transitive?

3. Given A = {1,2,3,4} and B = {x,y,z}. Let R be the following relation from A to B:
R = {(1, y), (1, z), (3, y), (4, x), (4, z)}
(a) Determine the matrix of the relation.
(b) Draw the arrow diagram of R.
(c) Find the inverse relation R1 of R.
(d) Determine the domain and range of R.

4. A license plate has 5 places, each having an alphanumeric value; how many license plates are we allowed to make? (repeating allowed)

5. Use Euclidian Algorithm to figure:
gcd(60,26)

Explanation / Answer

1) Consider Pk : 2 + 4 + · · · + 2k = k(k + 1)

Next, we state Pk+1, and use the induction hypothesis (the assumption that Pk is true) to prove that Pk+1 holds as well.

Pk+1 : 2 + 4 + · · · + 2k + 2(k + 1) = (k + 1)(k + 2)

To prove that Pk+1 holds, we will start with the expression on the left-hand side of Pk+1, and show that it is equal to the expression on the right-hand side. 2 + 4 + · · · + 2k + 2(k + 1)

Left-hand side of Pk+1 = k(k + 1) + 2(k + 1)

Induction hypothesis = k 2 + k + 2k + 2

Expand = k 2 + 3k + 2

Combine like terms = (k + 1)(k + 2) Factor

We see that the result, (k + 1)(k + 2), is the expression on the right-hand side of Pk+1.

Thus, by mathematical induction, Pn is true for all natural numbers n.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.