generic math (n1) (2n 1)(2n +3)/3 whenever n is Question 2. Prove that 1232+52 +

Question

generic math

(n1) (2n 1)(2n +3)/3 whenever n is Question 2. Prove that 1232+52 +... +(2)2 a nonnegative integer rove that 12 32 wnenever nis Question 3. Prove that 1 . 11+2 . 21+ . . . + n . n!-(n + 1)1-1, whenever n is a positive integer (Recall that if k is a positive integer then k factorial is k-k·(k-1) . 2 . 1 .) Question 4. The Gossip Problem: Suppose there are n people in a group, each aware of one scandal no one else in the group knows about. These people communicate by telephone; when two people in the group talk, they share information about all scandals each knows about. For example, on the first call, two people share information, so by the end of the call, each of these people knows about two scandals. The gossip problem asks for G(n), the minimum number of telephone calls that are needed for all n people to learn about all the scandals. (i) (ii) Find G(1), G(2), G(3), and G(4) Use mathematical induction to prove that G(n)-2n-4 for n-4·Hint: In the inductive step, have a new person call a particular person at the start and at the end Question 5. Which dollar amounts of money can be formed using using just two-dollar bills and five-dollar bills? Prove your answ er using strong induction

Explanation / Answer

Proving by induction:

let p(n) : 1^2 +2^2 +.............................+n^2

for n=1

lhs =>1

rhs ==>1.2.3/6 =>1

hence proved

Assume it is true for n= k

proving it to be true for n=k+1

1^2 +2^2 +k^2+(k+1)^2

lhs simplifies to :

k(k+1)(2k+1)/6 +(k+1)^2

=>k(k + 1)(2k + 1) + 6(k + 1)^2 /6

=>(k + 1)[k(2k + 1) + 6(k + 1)] /6

=>  (k + 1)(2k^2+ 7k + 6)/ 6

=> (k + 1)(k + 2)(2k + 3)/ 6

hence true for n=k+1

hence valid

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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