Answers must be correct. Or else it will be flagged. All sub-parts need to be an

Question

Answers must be correct. Or else it will be flagged. All sub-parts need to be answered with step by step process showing all work and reasoning.

YOU MUST PROVIDE ALL ANSWERS AS PER THE QUESTIONS.

DON'T PROVIDE WRONG ANSWERS AND DON'T ANSWER IF YOU DON'T WANT TO ANSWER ALL SUB-PARTS. INCOMPLETE ANSWERS WILL BE FLAGGED

DISCRETE STRUCTURES

Don't forget to consider the case when n<k. In this case (n choose k)=0.

Question 2 (12 points) Recall()-b. Prove or disprove each st n+1 a) For all non-negative nte z, (i) C 1) b) For all non-negative n, k Z, C)

Explanation / Answer

a) (n,k) <= (n+1,k+1)

    (n, k) = n!/(k!(n-k)!)

    (n+1,k+1) = (n+1)! /(k+1)! (n-k-1)!
              =   n! (n+1)/ k!(k+1) * ((n-k)!/(n-k)
              =   (n!/k!(n-k)!) * ((n-k)(n+1)/(k+1))-----(1)

    If (n < k) so (n, k) = 0   so (1) is also 0 so equality holds for n < k

    if (n > k)     then the factor ((n-k)(n+1)/(k+1)) will be > 1 and hence
                   (n+1,k+1) > (n,k)

    So a) hold

b) It does not hold because when n < k , we have the equality as (n,k) = 0 and
   (n+1,k+1) = 0

c)    (n1,k1) = n1!/((n1-k1)! k1!

      (n2,k2) = n2!/((n2-k2)! k2!

       (n1,k1) > (n2,k2)-------(3)

       (3) does not hold because we have proved in a) that (n+1,k+1) >= (n,k) which
        is exactly the condition required in c) but just ">" is not enough as
        if k1 > n1 and k2 > n2 then both will be 0 and equal.

              

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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