2.1.1 Prove, using induction but also without it, that n(n+1) is an even number

Question

2.1.1 Prove, using induction but also without it, that n(n+1) is an even number for every nonnegative integer n

2.1.2 Prove by induction that the sum of the first n positive integers is n(n + 1)/2

2.1.3 Observe that the number n(n + 1)/2 is the number of handshakes among n + 1 people. Suppose that everyone counts only handshakes with people older than him/her (pretty snobbish, isn’t it?). Who will count the largest number of handshakes? How many people count 6 handshakes? (We assume that no two people have exactly the same age.) Give a proof of the result of Exercise 2.1.2, based on your answer to these questions.

2.1.4 Give a proof of Exercise 2.1.2, based on Figure 2.1.

Figure 2.1 (1+3+ ··· + (2n 3) + (2n 1) = n2.)

2.1.5 Prove the following identity: 1 · 2+2 · 3+3 · 4 + ··· + (n 1) · n = (n 1) · n · (n + 1) 3 .

Exercise 2.1.2 relates to a well-known anecdote from the history of mathematics. Carl Friedrich Gauss (1777–1855), one of the greatest mathematicians of all times, was in elementary school when his teacher gave the class the task to add up the integers from 1 to 1000. He was hoping that he would get an hour or so to relax while his students were working. (The story is apocryphal, and it appears with various numbers to add: from 1 to 100, or 1900 to 2000.) To the teacher’s great surprise, Gauss came up with the correct answer almost immediately. His solution was extremely simple: Combining the first term with the last, you get 1 + 1000 = 1001; combining the second term with the last but one, you get 2 + 999 = 1001; proceeding in a similar way, combining the first remaining term with the last one (and then discarding them) you get 1001. The last pair added this way is 500 + 501 = 1001. So we obtained 500 times 1001, which makes 500500. We can check this answer against the formula given in exercise 2.1.2: 1000 · 1001/2 = 500500.

2.1.6 Use the method of the young Gauss to give a third proof of the formula in exercise 2.1.2

2.1.7 How would the young Gauss prove the formula (2.1) for the sum of the first n odd numbers?

2.1.8 Prove that the sum of the first n squares 1+4+9+ ··· + n2 is n(n + 1)(2n + 1)/6.

2.1.9 Prove that the sum of the first n powers of 2 (starting with 1 = 20) is 2n 1.

Explanation / Answer

(According to Chegg policy, only four subquestions will be answered. Please post the others in another question)

2.1.1: Using induction:

For n=1, we have n(n+1) = 1*2 =2 which is even.

Let us assume the result holds for n=k i.e k(k+1) is even

=> k2 + k is even.

We shall prove that it is true for n=k+1 as well

(k+1)(k+2)

= k2+k+2k+2

= k2+k+ 2(k+1)

Since k2+k is even and 2(k+1) is even, (k+1)(k+2) is also even

So by induction, the given result holds.

Without using induction

There are two cases:

case (1): n is even. Let n=2k

Then n(n+1) = 2k(2k+1) = 2[k(2k+1)] which is divisible by 2 and hence even.

case (2): n is odd. Let n=2k+1

Then n(n+1) = (2k+1)(2k+2) = 2[(2k+1)(k+1)] which is divisible by 2 and hence even.

So n(n+1) is even.

2.1.2:

For n=1, Sum = 1 = 1*2/2

Let us assume the result holds for some M,

i.e Sum(M) = M(M+1)/2

We need to prove that it holds for M+1 as well.

Sum(M+1) = Sum(M) + (M+1)

=>Sum(M+1) = M(M+1)/2 + (M+1)

=>Sum(M+1) = (M+1) [M/2 +1]

=>Sum(M+1) = (M+1) (M+2)/2

=>Sum(M+1) = (M+1) (M+1+1)/2

which is the expected form

2.1.8:

For n=1, Sum = 1 = 1*2*3/6

Let us assume the result holds for some M,

i.e Sum(M) = M(M+1)(2M+1)/6

We need to prove that it holds for M+1 as well.

Sum(M+1) = Sum(M) + (M+1)2

=>Sum(M+1) = M(M+1)(2M+1)/6 + (M+1)2

=>Sum(M+1) = (M+1) [M(2M+1)/6 +M+1]

=>Sum(M+1) = (M+1) [(2M2+M+6M+6)/2]

=>Sum(M+1) = (M+1) [(2M2+7M+6)/2]

=>Sum(M+1) = (M+1) [(2M+3)(M+2)/2]

=>Sum(M+1) = (M+1) (M+1+1)(2(M+1)+1)/2

which is of the expected form

2.1.9:

The sum of first n powers of 2

= 20 + 21 + 22 + .....+ 2n

Since the above terms form a G.P, the sum is

a (rn-1) / (r-1)

a= 1 and r =2

=> Sum = 1 (2n-1)/(2-1)

=> Sum = 2n-1

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

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