# CS111 Homework Assignment 1

Problem 1: (a) You are eagerly waiting for the delivery of your smart phone. For each day the delivery is late, the phone company compensates you by giving you coupons. The number of coupons you get for each day is equal to the number of days the delivery is late. For example, if your phone is late $$2$$ days, you get $$1$$ coupon for the first day and $$2$$ coupons for the second day.

Use a summation notation $$\sum$$ to give the formula for the total number of coupons received in the first $$k$$ days after the delivery was due. Then give a closed-form formula (without the $$\sum$$ symbol) for this number.

(b) The coupons turn out to be more valuable than you thought. Each coupon is worth $$\1$$ the day you receive it, but since then its value doubles after each day. For example, if the phone is late $$3$$ days, the coupon for the first day will be now worth $$\4$$, each of the two coupons for the second day will be worth $$\2$$, while the three coupons for the third day will be worth $$\1$$.

Let $$W(n)$$ be the total value of coupons collected if the delivery was $$n$$ days late. Give the formula (using the summation notation) for $$W(n)$$.

(c) Derive a closed-form expression for $$W(n)$$.

(d) Finally, give the asymptotic value of $$W(n)$$ using the $$\Theta$$-notation.

Include a brief justification for each step. If you need any summation formulas for this problem, you are allowed to look them up.

Solution 1: (a) Since we are receiving one extra coupon for each consecutive day: $$1 + 2 + \ldots + (k-1) + k$$, the total coupons received for $$k$$ days can be represented as $$\sum\limits_{i=1}^k i$$ = $$\frac{k(k+1)}{2}$$

(b) Since we are still receiving one extra coupon for each consecutive day, $$\sum\limits_{i=1}^n i$$ can still represent the number of coupons received. However, the value of the coupons is: $$1 + 2 + 4 + \ldots+ (n-1) + 2(n-1)$$ which can be represented as $$\sum\limits_{i=1}^n 2^{n-i}$$. We must multiply the quantity and the value together during each sum to get the total value resulting in: $$W(n) = \sum\limits_{i=1}^n i*2^{n-i}$$

(c) For $$n = 1$$ through $$n = 6$$,

• $$W(1) = 1$$

• $$W(2) = 4$$

• $$W(3) = 11$$

• $$W(4) = 26$$

• $$W(5) = 57$$

We know that the closed form expression should involve a value slightly larger than $$2^n$$, so we try the same $$n$$ values for $$2^{n+1}$$ and get:

• $$2^{1+1} = 4$$

• $$2^{2+1} = 8$$

• $$2^{3+1} = 16$$

• $$2^{4+1} = 32$$

• $$2^{5+1} = 64$$

The difference between $$2^{n+1}$$ and $$W(n)$$ appears to be $$-n-2$$ for each term, so the closed form expression for $$W(n)$$ must be $$\sum\limits_{i=1}^n i*2^{n-i} = 2^{n+1}-n-2$$. We can prove that this expression is correct using induction.

Proof:
Base Case: For $$W(1)$$, $$2^{1+1}-1-2 = 1$$ which is correct since $$W(1) = 1$$.
Assume $$W(k) = 2^{k+1}-k-2$$, we must show that $$W(k+1) = 2^{k+2}-k-3$$
Based off of the sequence $$W(n)$$

• $$W(1) = 1$$

• $$W(2) = 4$$

• $$W(3) = 11$$

• $$W(4) = 26$$

• $$W(5) = 57$$

We see that each term $$W(k+1) = 2W(k) + (k+1)$$ so,
$$W(k+1) = 2(2^{k+1}-k-2) + (k+1)$$
$$W(k+1) = 2^{k+2}-2k-4+k+1$$
$$W(k+1) = 2^{k+2}-k-3$$
Therefore, $$W(n) = 2^{n+1}-n-2$$
Q.E.D.

(d) First, we will find the lower bound for $$W(n) = 2^{n+1}-n-2$$

After removing constants, we find that
$$2^{n}-n \geq 2^n - \frac{2^n}{2}$$ which is true for $$n > 2$$
Since $$2^n-\frac{2^n}{2}$$ belongs to $$\Omega(2^n)$$, $$W(n)$$ must as well since it is greater than or equal to $$2^n-\frac{2^n}{2}$$

Now we will find the upper bound for $$W(n) = 2^{n+1}-n-2$$

After removing constants,
$$2^{n}-n \leq 2^n$$, therefore, $$W(n)$$ belongs to $$\textit{O}(2^n)$$

Since $$W(n)$$ belongs to both $$\Omega(2^n)$$ and $$\textit{O}(2^n)$$,
$$W(n) = \theta(2^n)$$

Problem 2: Prove that there is an integer $$c>0$$ such that the following inequality holds for all $$n\ge c$$: $2^n + 3^n +4^n \le 5^n.$ Then explain how this implies that $$2^n+3^n+4^n = O(5^n)$$.

Hint: By hand, find the smallest $$c$$ for which $$n=c$$ satisfies this inequality, and then prove by induction that it holds for all $$n \ge c$$.

Solution 2:
Base Case: For $$n=3$$ $$2^3+3^3+4^3\leq5^3$$
$$99\leq125$$, so the inequality is true for $$n=3$$

Assume $$2^k+3^k+4^k\leq5^k$$, we must show that $$2^{k+1}+3^{k+1}+4^{k+1}\leq5^{k+1}$$
$$2^k+3^k+4^k\leq5^k$$ First, we multiply both sides by $$5$$
$$5(2^k+3^k+4^k)\leq5*5^k$$
$$5*2^k+5*3^k+5*4^k\leq5*5^k$$
We can replace each $$5$$ with the value of the coefficient for each term. This still keeps the inequality true.
$$2*2^k+3*3^k+4*4^k\leq5*5^k$$
$$2^{k+1}+3^{k+1}+4^{k+1}\leq5^{k+1}$$
Therefore, the inequality must hold for $$n\geq c$$, where $$c=3$$
Q.E.D

This implies that $$2^n+3^n+4^n = O(5^n)$$ because for $$n\geq c$$, $$2^n+3^n+4^n$$ is bounded by and never exceeds $$5^n$$. Therefore, $$2^n+3^n+4^n = O(5^n)$$.