In class practice

$x$ is one of the cities
$S=$ {cities with roads to $x$}
$T=$ {cities with roads coming from $x$}

Proof. We wish to prove the open sentence:
$P(n):n=5x+7y$ for some $x,y\in \mathbb{Z}$, such that $x,y\ge 0$, $n\in \mathbb{N}$, $n\ge 24$
We work by induction.
Base Cases:
We see that
24 = 5(2) + 7(2)
25 = 5(5) + 7(0)
26 = 5(1) + 7(3)
27 = 5(4) + 7(1)
28 = 5(0) + 7(4)

Inductive Step.
Let $k\in \mathbb{Z}$, $k\ge 28.$ Assume that $P(j)$ is true for all $24\le j\le k$.

We aim to prove $P(k+1)$ is true. By assumption, $P(k-4)$ is true. That means there are integers $x,y\ge 0$ such that $k-4=5x+7y$. Hence

Since $x,y\in \mathbb{Z}$ and $x+1>0$ we $P(k+1)$ is true thus by mathematical induction P(n) is true for all $n\in \mathbb{N}$.

HW 15

E 15.1

E 15.2
A --> C --> B --> D --> E --> F --> G --> H --> I

E 15.3
a)
Proof:
We wish to prove the open sentence:

$P(n):n=3x+8y$ for some $x,y\in \mathbb{Z}$ such that $x,y\ge 0$, $n>13$ where $x,y$ may depend on $n$.

Base Cases:
We see that
14 = 3(2) + 8(1)
15 = 3(5) + 8(0)
16 = 3(0) + 8(2)

Hence P(14), P(15), P(16) are true.

Inductive step:
Let $k\in \mathbb{Z},k\ge 16$. Assume $P(j)$ is true for all $14\le j\le k$.

We aim to prove $P(k+1)$ is true. By assumption $P(k-2)$ is true. This means that there are integers $x,y\ge 0$ such that $k-2=3x+8y$. Thus

Since $x,y\in \mathbb{Z}$ and $x+1>0$ we see $P(k+1)$ is true. Thus, by mathematical induction $P(n)$ is true for all $n\in \mathbb{N}$. $◻$

b)
Assume by way of contradiction that $13=3x+8y$ for some nonnegative integers $x,y$.

Since $x,y$ are nonnegative, when $x\ge 5$

Thus $x<4$. Thus $x\in \{0,1,2,3\}$

Since $x,y$ are nonnegative, when $y\ge 2$. $3x+16>13$. So $y<2$. Thus $y\in \{0,1\}$

We have 8 cases remaining:

1. For $x=0$, $y=0$, the equation becomes $13=3(0)+8(0)=0$, which is not true.

2. For $x=1$, $y=0$, the equation becomes $13=3(1)+8(0)=3$, which is not true.

3. For $x=2$, $y=0$, the equation becomes $13=3(2)+8(0)=6$, which is not true.

4. For $x=3$, $y=0$, the equation becomes $13=3(3)+8(0)=9$, which is not true.

5. For $x=0$, $y=1$, the equation becomes $13=3(0)+8(1)=8$, which is not true.

6. For $x=1$, $y=1$, the equation becomes $13=3(1)+8(1)=11$, which is not true.

7. For $x=2$, $y=1$, the equation becomes $13=3(2)+8(1)=14$, which is not true.

8. For $x=3$, $y=1$, the equation becomes $13=3(3)+8(1)=17$, which is not true.

None of these combinations equal $13$, implying that for nonnegative integers $x,y$, $13$ cannot be expressed as $3x+8y$. Thus we have reached a contradiction.

Hence, we conclude that $13$ cannot be written as $3x+8y$ for any integers $x,y\ge 0$. $◻$

E 15.4
Proof. Let $n\in \mathbb{N}$. We wish to prove the open sentence:

$P(n):n=2^{k}m$ for some $k\in \mathbb{Z}$, $m\in ODD$ where $k,m$ may depend on $n$.

Base Cases:

We see

Hence P(1) and P(2) are true.

Inductive step:
Let $k\in \mathbb{Z}$, $k\ge 2$. Assume that $P(j)$ is true for all $1\le j\le k$. We aim to prove $P(k+1)$ is true.

There are two cases:
Case 1: even $k+1$

If $k+1$ is even, then we can write $k+1=2l$ for some $l\in \mathbb{Z}$, $l>0$.

By the inductive hypothesis, we know that $l$ can be written in the form $2^{m}n$ for some $m\in \mathbb{Z}$, $n\in \text{ODD}$.

Therefore, $k+1=2l=2(2^{m}n)=2^{m+1}n$, where $n\in \text{ODD}$.

So, $P(k+1)$ is true when $k+1$ is even.

Case 2: odd $k+1$

If $k+1$ is odd, then we can directly write $k+1=2^0(k+1)$.

Since $k+1$ is odd, $k+1\in \text{ODD}$.

Therefore, $P(k+1)$ is also true when $k+1$ is odd.

Hence, by mathematical induction, the statement $P(n)$ is true for all $n\in \mathbb{N}$. $◻$

E 15.5
Proof:
Let $n\in \mathbb{N}$, $n>43$. We wish to prove the open sentence:
$P(n):n=6x+9y+20z$ where $x,y,z\ge 0$, $x,y,z\in \mathbb{Z}$ and may be dependent on $n$.

Base Cases:
P(44) = $6\cdot 1+9\cdot 4+20\cdot 0$
P(45) = $6\cdot 5+9\cdot 0+20\cdot 0$
P(46) = $6\cdot 0+9\cdot 2+20\cdot 1$
P(47) = $6\cdot 2+9\cdot 3+20\cdot 0$
P(48) = $6\cdot 4+9\cdot 0+20\cdot 1$
P(49) = $6\cdot 0+9\cdot 1+20\cdot 2$

Hence, P(44), P(45), P(46), P(47), P(48) and P(49) are true.

Inductive step:
Let $k\in \mathbb{Z},k\ge 49$. Assume $P(j)$ is true for all $44\le j\le k$.

We aim to prove $P(k+1)$ is true. By assumption, $P(k-5)$ is true. This means that there are integers $x,y,z\ge 0$ such that $k-5=6x+9y+20z$. Thus

Since $x,y,z\in \mathbb{Z}$ and $x+1>0$ we see $P(k+1)$ is true. Thus, by mathematical induction $P(n)$ is true for all $n\in \mathbb{N}$. $◻$

Proof that 43 cannot be written this way:

First, note that $6x$ and $9y$ are multiples of $3$. Thus, if $x$ and $y$ are non-negative integers, $6x+9y$ will be a multiple of $3$.

Possible values for $z$ resulting in an $n<43$ are 0, 20, and 40.

For any values of $x$ and $y$, $6x+9y$ is a multiple of 3, hence $6x+9y$ will be one of $\{0,3,6,9,12,15,18,21,24,27,30,33,36,39,42,...\}$. It's clear that none of these values can be added to $0$ or $20$ or $40$ to yield $43$.

Therefore, there are no non-negative integers $x,y,z$ for which $43=6x+9y+20z$. $◻$

E 15.6
The largest postage that cannot be paid is 21 cents.

Proof:
Let $n\in \mathbb{N}$, $n>21$. Let $x,y,z$ represent the postage stamps that cost 4, 10, and 15 cents respectively.

We wish to prove the open sentence:
$P(n):n=4x+10y+15z$ where $x,y,z\ge 0$, $x,y,z\in \mathbb{Z}$ and may be dependent on $n$.

Base Cases:
P(22) = $4\cdot 3+10\cdot 1+15\cdot 0$
P(23) = $4\cdot 2+10\cdot 0+15\cdot 1$
P(24) = $4\cdot 6+10\cdot 0+15\cdot 0$
P(25) = $4\cdot 0+10\cdot 1+15\cdot 1$
P(26) = $4\cdot 4+10\cdot 1+15\cdot 0$
P(27) = $4\cdot 3+10\cdot 0+15\cdot 1$

Hence, P(22), P(23), P(24), P(25), P(26), and P(27) are true.

Inductive step:
Let $k\in \mathbb{Z},k\ge 27$. Assume $P(j)$ is true for all $22\le j\le k$.

We aim to prove $P(k+1)$ is true. By assumption, $P(k-5)$ is true. This means that there are integers $x,y,z\ge 0$ such that $k-5=4x+10y+15z$. Thus

Since $x,y,z\in \mathbb{Z}$ and $x+1>0$ we see $P(k+1)$ is true. Thus, by mathematical induction $P(n)$ is true for all $n\in \mathbb{N}$. $◻$

Since all amounts greater than 21 cents can be paid with 4, 10, and 15 cent stamps the largest amount that cannot be paid is 21 cents.

E 15.7
Proof.

Base Cases:
Consider the numbers 1, 2 and 3.

• 1 is itself a Fibonacci number.
• 2 is also a Fibonacci number.
• 3 can be written as the sum of two Fibonacci numbers (2 + 1).

Inductive Case:
Assume that every number $k$ can be written as a sum of distinct Fibonacci numbers. We want to show that this is also true for the number $k+1$.

To do that, we find the largest Fibonacci number, $F_m$, that is less than or equal to $k+1$. According to the properties of Fibonacci numbers, we know that $F_m\le k+1<F_{m+1}$.

We can express $k+1$ as $F_m+(k+1-F_m)$.

If $k+1-F_m=0$, then $k+1$ is already a Fibonacci number.

If $k+1-F_m>0$, then $k+1-F_m$ is a positive integer less than $F_m$.

By our inductive hypothesis, we can represent any number less than $F_m$ as a sum of distinct Fibonacci numbers. Therefore, $k+1-F_m$ can be written as a sum of Fibonacci numbers, each of which is smaller than $F_m$.

Thus, every number up to and including $k+1$ can be expressed as a sum of distinct Fibonacci numbers. By the principle of mathematical induction, every positive integer can be expressed as a sum of distinct Fibonacci numbers. $◻$