ECS020 midterm review

W2Q1

Rewriting expression in sum notation Let the following represent $P(n)$

$$1+2+2^2+\cdots +2^n=\sum _{n=0}^{n-1}{2}^n=2^{n+1}-1$$

basic induction

• base case: n = 0
  • $2^0=2-1=1$
• induction hypothesis
  • assume that the statement holds for an arbitrary $n\ge 0$
• induction step
  • we need to prove that $P(n+1)$

$$\begin{array}{rl}\sum _{n=0}^n{2}^n& =\sum _{n=0}^{n-1}{2}^n+2^n\\ & =2^n-1+2^n\\ & =2^{n+1}-1\end{array}\text{\hspace{1em}■}$$

W2Q2

Let the following be $P(n)$

$$n<2^n$$

for all positive integers $n$

Base Case

For $P(1)$, $1<2$, which is true.

Induction Hypothesis

Assume that, for an arbitrary $n\ge 1$, $P(n)$ holds.

Induction Step

We need to prove that $P(n+1)$ holds.

$$\begin{array}{rl}n+1& <2^{n+1}\\ n& <2^{n+1}-1\end{array}$$

Based on $P(n)$ we know that $n<2^n$. Therefore we can prove $P(n+1)$ if we can show that $2^{n+1}-1\ge 2^n$.

$$\begin{array}{rl}{2}^{n+1}-1& >2^n\\ 2^{n+1}& >2^n+1\end{array}$$

We know that $2^n>1$ for any $n\ge 1$, so the above is true. $■$

W2Q3

Let the following be $P(n)$

$$3\mid n^3-n$$

for any positive integer $n$. that is, $\frac{n^3-n}{3}=k$ where $k$ is an integer.

Base Case

For $P(1)$, we have

$$\frac{1-1}{3}=0$$

and $3\mid 0$, making the base case true.

Induction Hypothesis

We assume that for any arbitrary $n\ge 1$, $P(n)$ holds.

Induction Step

We need to prove that $P(n+1)$ holds.

$$\begin{array}{rl}(n+1{)}^3-(n+1)& =n^3+3n^2+3n+1-n-1\\ & =(n^3-n)+3(n^2+n)\end{array}$$

From $P(n)$ we know that $n^3-n$ divided by 3 is $k$. Then we have:

$$(n+1{)}^3-(n+1)=3(k+n^2+n)$$

which is divisible by three. $■$

W3P1Q1

Let $P(n)$ denote that if $n$ is an integer greater than 1, then $n$ can be written as the product of primes.

Base Case

We know that for $P(2)$ the number two can be written as the product of itself.

Induction Hypothesis

We assume all cases $P(2),P(3),\dots ,P(n)$ holds.

Induction Step

We need to prove that $P(n+1)$. If $n+1$ is prime, then it can be written as the product of itself. If $n+1$ is not prime, then by definition it must have one factor that is neither 1 or itself. Let’s call the factor $p$ and denote $\frac{n+1}{p}$ as $q$. Since $k<n+1$ and $q<n+1$, we know that $P(p)$ and $P(q)$ hold, and that $n+1$ can be represented as the product of primes, namely the product of primes that make up $p$ and $q$.

W3P1Q2

Let $P(n)$ denote that a certain combination of 3-cent and 10-cent stamps can represent an $n$-cent postage, for any positive integer $n\ge 18$.

Base Case

03 = 0 x 10 + 1 x 3
04 = 
05 = 
06 = 0 x 10 + 2 x 3
07 = 
08 = 
09 = 0 x 10 + 3 x 3
10 = 0 x 10 + 1 x 10
11 = 
12 = 0 x 10 + 4 x 3
13 = 1 x 10 + 1 x 3
14 = 
15 = 0 x 10 + 5 x 3
16 = 1 x 10 + 2 x 3
17 = 
18 = 6 x 3
19 = 1 x 10 + 3 x 3
20 = 2 x 10 + 0 x 3
...

Induction Hypothesis

Assume that $P(18),\dots ,P(n)$ holds for any positive integer $n\ge 20$.

Induction Step

We need to prove $P(n+1)$.

We know that $n+1-3\ge 20-2$, so $P(n-2)$ holds. We can add a 3-cent stamp to that to represent $n+1$.

W3P1Q3

Let $P(n)$ denote that any positive integer $n$ can be written as the sum of distinct powers of 2, that is.

Base Case

For $P(1)$, we have $1=2^0$. For $P(2)$, we have $2=2^1$. For $P(3)$, we have $3=2^1+2^0$ For $P(4)$, we have $4=2^2$ For $P(5)$, we have $5=2^2+2^0$ For $P(6)$, we have $6=2^2+2^1$ For $P(7)$, we have $7=2^2+2^1+2^0$ For $P(8)$, we have $8=2^3$ For $P(9)$, we have $9=2^3+2^0$ For $P(10)$, we have $10=2^3+2^1$

Induction Hypothesis

Assume that $P(1)$ to $P(n)$ for any integer $n\ge 4$

Induction Step

We need to show that $P(n+1)$ holds.

If $n+1$ is odd, we can represent $n+1$ as $n+2^0$. Otherwise if $n+1$ is even, we know $P\left(\frac{n+1}{2}\right)$ holds, and we can multiply the sum that represent $\frac{n+1}{2}$ by 2 to get the expression for $n+1$, since multiplying the sum is equivalent to adding 1 to each exponent.

W3P2Q1

We first prove that if $⟨x,y⟩=⟨u,v⟩$, then $x=u$ and $y=v$ Rewriting the ordered pairs as sets: $\{x,\{x,y\}\}=\{u,\{u,v\}\}$ Whatever look at the solution So the initial assumption must be false, and the proposition to be proved is true.

We then prove that if $x=y$ and $y=v$, then $⟨x,y⟩=⟨u,v⟩$ Direct proof: The two sets $\{x,\{x,y\}\}$ and $\{u,\{u,v\}\}$ are equal to another if $x=u$ or $y=v$ So the proposition to be proved is true.

Therefore $⟨x,y⟩=⟨u,v⟩$ if and only if $x=y$ and $y=v$

W3P2Q2

$$\begin{array}{rl}\overline{A\cup B}& =\overline{\{x:x\in A\vee x\in B\}}\\ & =\{x:x\notin A\wedge x\notin B\}\\ & =\{x:x\notin A\}\cap \{x:x\notin B\}\\ & =\overline{A}\cap \overline{B}\end{array}$$

W3P2Q3

$A\times C=\{⟨x,y⟩:x\in A\wedge y\in C\}$ $B\times D=\{⟨x,y⟩:x\in B\wedge y\in D\}$

Since we know that $A\subseteq B\wedge C\subseteq D$, then every ordered pair $⟨x,y⟩\in A\times C$ also satisfies $x\in B\wedge y\in D$, meaning that each ordered pair is an element of $B\times D$, implying that $A\times C\subseteq B\times D$.