Combinatorics

6.1.6.1 Various formulas are possible. Most simply, the sequence can be described by the recurrence relation $\displaystyle s_1=4\text{,}$ $\displaystyle s_i=2s_{i-1}+1$ for $\displaystyle i \ge 2\text{.}$ With this description, the next term is $\displaystyle s_5=2(39)+1=79\text{.}$

6.1.6.3 Adjusting the recurrence relation from Example 6.1.5, we obtain the new relationThis simplifies to $\displaystyle r_n=1.01(r_{n-1}-20)\text{.}$ We still have $\displaystyle r_0=2000\text{.}$ We now haveStavroula is (marginally) losing money from the beginning. This situation will only get worse as her starting balance each year dwindles.

6.2.6.1 Proof. Base case: $\displaystyle n=1\text{.}$ We have $\displaystyle b_1=5$ and $\displaystyle 5+4(1-1)=5\text{,}$ so $\displaystyle b_n=5+4(n-1)$ when $\displaystyle n=1\text{.}$

Inductive step: We begin with the inductive hypothesis. Let $\displaystyle k\ge 1$ be arbitrary, and suppose that the equality holds for $\displaystyle n=k\text{;}$ that is, assume that $\displaystyle b_k=5+4(k-1)\text{.}$

Now we want to deduce that

Using the recursive relation, we have $\displaystyle b_{k+1}=b_k+4$ since $\displaystyle k+1 \ge 2\text{.}$ Using the inductive hypothesis, we have $\displaystyle b_k=5+4(k-1)\text{.}$ Putting these together gives

as desired. This completes the proof of the inductive step.

By the Principle of Mathematical Induction, $\displaystyle b_n=5+4(n-1)$ for every $\displaystyle n \ge 1\text{.}$ ◾

6.2.6.3 Proof. Base case: $\displaystyle n=0\text{.}$ We have $\displaystyle 0!=1$ (by definition) and $\displaystyle n=0\text{,}$ so $\displaystyle n! =1 \ge 0=n\text{.}$ Thus, $\displaystyle n!\ge n$ when $\displaystyle n=0\text{.}$

Inductive step: We begin with the inductive hypothesis. Let $\displaystyle k \ge 0$ be arbitrary, and suppose that the inequality holds for $\displaystyle n=k\text{;}$ that is, assume that $\displaystyle k! \ge k\text{.}$

Now we want to deduce that $\displaystyle (k+1)! \ge k+1\text{.}$ Using the definition of factorial, we have $\displaystyle (k+1)!=(k+1)k!$ since $\displaystyle k+1 \ge 0+1=1\text{.}$ Using the inductive hypothesis, we have $\displaystyle k! \ge k\text{.}$ Putting these together gives

If $\displaystyle k \ge 1\text{,}$ then

and we are done. If $\displaystyle k=0\text{,}$ then $\displaystyle (k+1)!=1!=1 =k+1$ and again the inequality is satisfied. This completes the proof of the inductive step.

By the Principle of Mathematical Induction, $\displaystyle n! \ge n$ for every $\displaystyle n \ge 0\text{.}$ ◾

6.3.5.2 Proof. Base cases: We will have four base cases: $\displaystyle n=12\text{,}$ $\displaystyle n=13\text{,}$ $\displaystyle n=14\text{,}$ and $\displaystyle n=15\text{.}$

For $\displaystyle n=12\text{,}$ I can get $12 onto my gift card by buying three increments of $4, since $\displaystyle 4+4+4=12\text{.}$

For $\displaystyle n=13\text{,}$ I can get $13 onto my gift card by buying two increments of $4 and one of $5, since $\displaystyle 4+4+5=13\text{.}$

For $\displaystyle n=14\text{,}$ I can get $14 onto my gift card by buying two increments of $5 and one of $4, since $\displaystyle 4+5+5=14\text{.}$

For $\displaystyle n=15\text{,}$ I can get $15 onto my gift card by buying three increments of $5, since $\displaystyle 5+5+5=15\text{.}$

Inductive step: We begin with the (strong) inductive hypothesis. Let $\displaystyle k \ge 15$ be arbitrary, and assume that for every integer $\displaystyle i$ with $\displaystyle k-3 \le i \le k\text{,}$ I can put $$\displaystyle i$ onto my gift card.

Now I want to deduce that I can put $$\displaystyle (k+1)$ onto my gift card. Using the inductive hypothesis in the case $\displaystyle i=k-3\text{,}$ I see that add can put $$\displaystyle (k-3)$ onto my gift card by buying increments of $4 or $5. Now if I buy one additional increment of $4, I have put a total of $$\displaystyle (k-3+4)$ = $$\displaystyle (k+1)$ onto my gift card, as desired. This completes the proof of the inductive step.

By the (strong) Principle of Mathematical Induction, I can put any amount of dollars that is at least $12 onto my gift card. ◾