# Use a summation factor to solve the recurrence T0 = 5;2Tn = (n + 1)Tn−1 + 3 ·

Question

Discrete Mathematics – all 8 questions are properly formatted in the attached pdf.

1. Use a summation factor to solve the recurrence T0 = 5;2Tn = (n + 1)Tn−1 + 3 · (n + 1)!, for n > 0

2. Evaluate the sum nk=11 + (−1)kk4k2 − 1

3. Plot 3x as a function of x. Find a necessary and sufficient condition that dnxe =ndxe, in which n is a positive integer.

4. Prove that 6 divides n(n + 1)(2n + 1) for any integer n.

5. Prove that nk=02 knk= 3n.

6. You put m apples randomly in n baskets. Suppose each basket has unlimited capacity, what is the expected number of empty baskets?

7. Draw three connected graphs with 5 vertices and 4 edges such that none of the graphsyou drew is isomorphic to another. Argue that every connected graph with 5 vertices and 4 edges is isomorphic to one of the three graphs you drew.

8. What is wrong with the following proof? Theorem: x = −x for all x. Proof: x =√x2 =p(−x)(−x) = √−x√−x = (√−x)2 = −x.

Math UA 120

Final Exam

Due: 11:59 p.m., Monday, December 21, 2015

Send your solution to calvinz@cims.nyu.edu

Instructions: (1) This ﬁnal exam has 8 problems. Each problem is worth 4 points, and

the total score is 32 points. (2) You are welcome to collaborate with your friends, however,

you must write your own solution. (3) Please write your solution on a separate paper

and show all steps of your work. (4) Scan your completed solution into a single PDF ﬁle (not

separate image ﬁles), and send it to calvinz@cims.nyu.edu before or at 11:59 p.m., Monday,

December 21, 2015 (Eastern Time). (5) You will receive an email reply within 24 hours of

your submission. If you do not receive an email response, please resend your solution. (6)

If the instructor does not receive your ﬁnal exam by the due date and you did not provide

any valid reason, you will receive a zero for your ﬁnal exam.

1. Use a summation factor to solve the recurrence

T0 = 5;

2Tn = (n + 1)Tn−1 + 3 · (n + 1)!,

for n > 0.

2. Evaluate the sum

n

k=1

3.

n x ,

4.

5.

1 + (−1)k k

.

4k 2 − 1

Plot 3x as a function of x. Find a necessary and suﬃcient condition that nx =

in which n is a positive integer.

Prove that 6 divides n(n + 1)(2n + 1) for any integer n.

Prove that

n

2k

k=0

n

k

= 3n .

6. You put m apples randomly in n baskets. Suppose each basket has unlimited capacity,

what is the expected number of empty baskets?

7. Draw three connected graphs with 5 vertices and 4 edges such that none of the graphs

you drew is isomorphic to another. Argue that every connected graph with 5 vertices and 4

edges is isomorphic to one of the three graphs you drew.

8. What is wrong with the following proof?

Theorem: x√ −x for all x.

=

√ √

√

Proof: x = x2 = (−x)(−x) = −x −x = ( −x)2 = −x.

1

**30 %**discount on an order above

**$ 5**

Use the following coupon code:

CHRISTMAS