w2

1. Prove the opposite of the following statement: there is a positive integer \(n\) such that \(n^2\) is not the sum of the first \(n\) odd numbers

   Proof:

   The opposite of the following statement is: \(\forall n\in N\), \(n^2=1+3+5+...+m\)​

   Then \(1+3+5+...+m=\frac{(1+m)n}{2}\) (sum) and \(n=\frac{m+1}{2}\)(number of terms)

   This is equivalent to \(m=2n-1\), then \(1+3+5+...+m=\frac{(1+2n-1)n}{2}=\frac{2n^2}{2}=n^2\)

   Therefore \(\forall n\in N\), \(n^2=1+3+5+...+m\) which is the opposite of the following statement: there is a positive integer \(n\) such that \(n^2\) is not the sum of the first \(n\) odd numbers

2. \(\begin{array}{rcl}\text{Let }F_n\text{ be the sequence of Fibonacci numbers given by the equations}\\\\F_1=1,\quad F_2=1,\quad F_{n+1}=F_n+F_{n-1},\quad&n\ge2.\end{array}\)

   \(\begin{aligned}\text{Prove that }&F_n\text{ and }F_{n+1}\text{ are relatively prime for all }n\in\mathbb{N}.\end{aligned}\)

   Proof:

   Using modified induction

   • Basic step

   \(n=2,F_3=F_2+F_1\)

   \(F_3=1+1=2\), then \(F_3=2,F_2=1\)

   Since \(1\) and \(2\) are relatively prime, so \(F_2\) and \(F_3\) are relatively prime. - Inductive step

   Suppose \(F_{n+1}\text{ and }F_n\) are relatively prime,(Hypothesis) then \(gcd(F_{n+1},F_n)=1\)

   Then we need to prove \(F_{n+2}\text{ and }F_{n+1}\) are relatively prime

   Due to \(F_{n+2}=F_{n+1}+F_{n}\), we need to prove \(gcd(F_{n+1}+F_n,F_{n+1})=1\)

   By the theorem, \(gcd(F_{n+1},F_n)=1=m\cdot F_{n+1}+n\cdot F_n\).

   Then \(F_n=\frac{1-m\cdot F_{n+1}}{n}\)(\(m,n\in Z\))

   Then \(F_{n+1}+F_{n}=\frac{1-m\cdot F_{n+1}}{n}+F_{n+1}=\frac{1-m\cdot F_{n+1}+n\cdot F_{n+1}}{n}=\frac{n-m}{n}F_{n+1}+\frac{1}{n}\)

   Observe the above equation, we can construct that

   \(gcd(F_{n+1}+F_n,F_{n+1})=a\cdot (F_{n+1}+F_n)+b(F_{n+1 })\) (\(a,b\in Z\))

   Let \(a=n,b=m-n\)​

   We get \(gcd(F_{n+1}+F_n,F_{n+1})=n\cdot (\frac{n-m}{n}F_{n+1}+\frac{1}{n})+(m-n)F_{n+1}\\=(n-m)F_{n+1}+1+(m-n)F_{n+1}=1\)

   Therefore \(\begin{aligned}F_n\text{ and }F_{n+1}\text{ are relatively prime for all }n\in\mathbb{N}.\end{aligned}\)​

   ‍

3. Prove that the function \(f:(0,1]\to(0,1)\) given by

   \[ f(x)=\begin{cases}\frac{1}{n+1}&\text{if }x=\frac{1}{n},\quad n\in\mathbb{N}\\x&\text{if }x\notin\left\{\frac{1}{n}:n\in\mathbb{N}\right\}\end{cases} \]

   is bijective. Then, the sets (0,1] and (0,1) have the same cardinality

   Proof

   • First, we prove injection(Definition: if \(f(x_1)=f(x_2)\), then \(x_1=x_2\)).

   • Prove \(f(x)=\frac{1}{n+1}~~~\text{if }x=\frac{1}{n},\quad n\in\mathbb{N}\) is injective

     From above we know \(f(x)=\frac{1}{1+\frac{1}{x}}=\frac{x}{x+1}\), then take \(f(x_1)=f(x_2)\).(\(x_1,x_2=\frac{1}{n},\quad n\in\mathbb{N}\)​)

     Then \(\frac{x_1}{x_1+1}=\frac{x_2}{x_2+1}\)​

     \(x_1\cdot x_2+x_1=x_1\cdot x_2+x_2\)

     Obviously, \(x_1=x_2\)​ - Prove \(f(x)=x~~~\text{if }x\notin\{\frac{1}{n}:n\in\mathbb{N}\}\) is injective

     Take \(f(x_1)=f(x_2)\).(\(x_1,x_2\notin\{\frac{1}{n}:n\in\mathbb{N}\}\))

     Obviously, \(x_1=x_2\) - Prove \(f(x)=\begin{cases}\frac{x}{x+1}&\text{if }x=\frac{1}{n},\quad n\in\mathbb{N}\\x&\text{if }x\notin\left\{\frac{1}{n}:n\in\mathbb{N}\right\}\end{cases}\) is injective

     Take \(f(x_1)=f(x_2)\) (\(x_1=\frac{1}{n},~n\in\mathbb{N}\) and \(x_2\notin\{\frac{1}{n}:n\in\mathbb{N}\}\))

     Then \(\frac{x_1}{x_1+1}=x_2\)​

     Since \(x_1=\frac{1}{n_1}\), \(x_2\neq \frac{1}{n_2}\), then \(\frac{1}{1+n_1}\neq \frac{1}{n_2}\)

     Then \(1+n_1\neq n_2\), but \(n_1,n_2\in N\) which is possible equality

     Hence there does not exist \(f(x_1)=f(x_2)\)​

     Hence it is injection

     ‍

     Therefore, \(f(x)\) is injective - Then, we prove surjection(Definition: \(\forall y\in (0,1),\exist x\in(0,1] such~that~f(x)=y\) )

   • \(f(x)=\frac{1}{n+1}~~~\text{if }x=\frac{1}{n},\quad n\in\mathbb{N}\)

     From above we know \(f(x)=\frac{1}{1+\frac{1}{x}}=\frac{x}{x+1}\), then take \(f(x)=y\)

     Then \(\frac{x}{x+1}=y\) (\(x=\frac{1}{n}, n\in\mathbb{N}\))

     \(y=\frac{1}{1+n}\), then \(y\in\{\frac{1}{2},\frac{1}{3},\frac{1}{4},...\}\)​

     Hence if \(y\in\{\frac{1}{2},\frac{1}{3},\frac{1}{4},...\}\), there \(\exists x=\frac{1}{n}, n\in\mathbb{N}\) such that \(f(x)=y\)​ - \(f(x)=x~~~\text{if }x\notin\{\frac{1}{n}:n\in\mathbb{N}\}\)​

     Take \(f(x)=y\), then \(x=y\) for \(x\notin\{\frac{1}{n}:n\in\mathbb{N}\}\)

     Then \(y\in\{0<y<1|y\neq\frac{1}{2},\frac{1}{3},\frac{1}{4},...\}\)​

     Hence if \(y\in\{0<y<1|y\neq\frac{1}{2},\frac{1}{3},\frac{1}{4},...\}\), there \(\exists x\notin\{\frac{1}{n}:n\in\mathbb{N}\}\) such that \(f(x)=y\) - From above, we can conclude that

     If \(y\in\{0<y<1|y\neq\frac{1}{2},\frac{1}{3},\frac{1}{4},...\}\), there \(\exists x\notin\{\frac{1}{n}:n\in\mathbb{N}\}\) such that \(f(x)=y\)

     If \(y\in\{\frac{1}{2},\frac{1}{3},\frac{1}{4},...\}\), there \(\exists x=\frac{1}{n}, n\in\mathbb{N}\) such that \(f(x)=y\)

     Therefore, \(\forall y\in (0,1)\), \(\exists x\in(0,1]\) such that \(y=f(x)\)​

     Which means \(f(x)\) is surjective - Since \(f(x)\) is injective and surjective, \(f(x)\) is bijective

   Due to \(f:(0,1]\to(0,1)\) is bijective, the sets (0,1] and (0,1) have the same cardinality

   ‍

4. \(\begin{aligned}&\text{Prove that }\forall n\in\mathbb{N}\text{ we have}\\\\&\text{a. }\sum_{i=1}^n\frac{i2^i}{\left(i+1\right)\left(i+2\right)}=\frac{2^{n+1}}{n+2}-1&\end{aligned}\)

   Using induction

   • Basic step

   If \(n=1\), \(\begin{aligned}&\sum_{i=1}^1\frac{i2^i}{\left(i+1\right)\left(i+2\right)}=\frac{1\cdot2^1}{(1+1)(1+2)}=\frac{2}{2\cdot 3}=\frac{1}{3}&\end{aligned}\)

   And \(\frac{2^{n+1}}{n+2}-1=\frac{2^{1+1}}{1+2}-1=\frac{4}{3}-1=\frac{1}{3}\)

   True

   • Inductive step

   Suppose \(\begin{aligned}&\sum_{i=1}^n\frac{i2^i}{\left(i+1\right)\left(i+2\right)}=\frac{2^{n+1}}{n+2}-1&\end{aligned}\)is true,

   We need to prove \(\begin{aligned}&\sum_{i=1}^{n+1}\frac{i2^i}{\left(i+1\right)\left(i+2\right)}=\frac{2^{n+2}}{(n+1)+2}-1&\end{aligned}\)

   \(\begin{aligned}&\sum_{i=1}^{n+1}\frac{i2^i}{\left(i+1\right)\left(i+2\right)}=\sum_{i=1}^n\frac{i2^i}{\left(i+1\right)\left(i+2\right)}+\frac{(n+1)\cdot 2^{n+1}}{(n+1+1)(n+1+2)}&\end{aligned}\)

   \(\begin{aligned}&=\frac{2^{n+1}}{n+2}-1+\frac{(n+1)\cdot 2^{n+1}}{(n+1+1)(n+1+2)}\\&=\frac{2^{n+1}}{n+2}-1+\frac{(n+1)\cdot2^{n+1}}{(n+2)(n+3)}\\&=\frac{(n+3)\cdot2^{n+1}-(n+2)(n+3)+(n+1)\cdot2^{n+1}}{(n+2)(n+3)}\\&=\frac{2^{n+1}(n+3+n+1)-(n+2)(n+3)}{(n+2)(n+3)}\end{aligned}\)

   \(\begin{aligned}&=\frac{2^{n+1}(2n+4)-(n+2)(n+3)}{(n+2)(n+3)}\\&=\frac{2^{n+2}(n+2)-(n+2)(n+3)}{(n+2)(n+3)}\\&=\frac{(n+2)(2^{n+2}-n-3)}{(n+2)(n+3)}\end{aligned}\)

   \(\begin{aligned}&=\frac{2^{n+2}-(n+3)}{n+3}\\&=\frac{2^{n+2}}{n+3}-1\\&=\frac{2^{n+2}}{(n+1)+2}-1\end{aligned}\)

   Therefore it is true for \(n+1\)​

   Hence, \(\begin{aligned}&\forall n\in\mathbb{N}~~~\sum_{i=1}^n\frac{i2^i}{\left(i+1\right)\left(i+2\right)}=\frac{2^{n+1}}{n+2}-1\end{aligned}\)

   ‍

   \(\begin{aligned}&\text{b. }\prod_{i=1}^n\frac{n+i}{2i-3}=2^n\left(1-2n\right)&\end{aligned}\)​

   Using induction

   • Basic step

   If \(n=1\), \(\begin{aligned}&\prod_{i=1}^n\frac{n+i}{2i-3}=\frac{1+1}{2-3}=\frac{2}{-1}=-2&\end{aligned}\)

   And \(2^n(1-2n)=2^1(1-2)=-2\)

   True - Inductive step

   Suppose \(\begin{aligned}&\prod_{i=1}^n\frac{n+i}{2i-3}=2^n\left(1-2n\right)&\end{aligned}\)is true

   We need to prove \(\begin{aligned}&\prod_{i=1}^{n+1}\frac{(n+1)+i}{2i-3}=2^{n+1}\left(1-2({n+1})\right)&\end{aligned}\)​

   \(\begin{aligned}&\prod_{i=1}^{n+1}\frac{(n+1)+i}{2i-3}=\prod_{i=1}^{n}\frac{(n+1)+i}{2i-3}\cdot\frac{(n+1)+(n+1)}{2(n+1)-3}&\end{aligned}\)​

   \(\begin{aligned}&=\frac{2n-3}{n+1}\cdot2^{n}(1-2{n})\cdot\frac{(n+1)+n}{2n-3}\cdot\frac{(n+1)+(n+1)}{2(n+1)-3}\\&=\frac{2^{n}(1-2n)}{n+1}\times\frac{(n+1)+n}{2(n+1)-3}\times2(n+1)\\&=\frac{2^{n}(1-2n)\times(2n+1)\times2}{2n-1}\\&=-2^{n}(2n+1)\times2\\&=2^{n+1}(1-2(n+1))\end{aligned}\)

   Therefore it is true for \(n+1\)​ - Hence, \(\begin{aligned}\forall n\in\mathbb{N}~~~\prod_{i=1}^n\frac{n+i}{2i-3}=2^n\left(1-2n\right)\end{aligned}\)​

5. Prove that any natural number \(n\) greater than \(3\)​ can be written in the form \(n=2k+5\ell\text{ with }k,\ell\in\mathbb{N}_0\)

Using induction

• Basic step

If \(n=4,4=2\cdot 2+5\cdot 0\) true - Inductive step

Suppose \(n=2k_0+5\ell_0=2(k_0+\ell_0)+3\ell_0\text{ with }k,\ell\in\mathbb{N}_0\)

Then, we need to prove \(n+1=2k_1+5\ell_1\text{ with }k_,\ell\in\mathbb{N}_0\)

\(n+1=2k_0+5\ell_0+1=2k_0+2\ell_0+3\ell_0+1=2k_0+2(\ell_0-1)+3(\ell_0+1)=2(k_0+\ell_0-1)+3(\ell_0+1)\)​

\(=2(k_0+\ell_0-1)+3(\ell_0+1)=2(k_0-2+\ell_0+1)+3(\ell_0+1)\\\text{( From the basic step, we know }k_0\geq 2~\text{ so, let }k_1=k_0-2\text{ and }\ell_1=\ell_0+1)~~~~~~~~~~~~\)​

We get \(2(k_1+\ell_1)+3(\ell_1)=2k_1+5\ell_1\)​

Hence it is true for \(n+1\)​ - Therefore, any natural number \(n\) greater than \(3\) can be written in the form \(n=2k+5\ell\text{ with }k,\ell\in\mathbb{N}_0\)

‍

‍