Assignment 2 (pdf)

Make sure to write complete proofs. Try to avoid skipping steps. Write clear sentences.

1. For each of the following statements, if the statement is true then say so and provide a proof. If it is false then say so and provide an example/proof. All variables involved are supposed to be natural numbers.
   1. For all n and m, if \(n+m\) is odd then exactly one of n,m is odd.
   2. For every n there exists an m such that \(n+m\) is odd.
   3. There exists an m such that for every n we have that \(n+m\) is odd.
   4. For every m there exists an n so that \(n^2 = m+2\).
   5. For all n, m we have that \(n\neq m\).
   6. There exists an n so that for all m we have that \(n\neq m\).
   7. For every n there is a k so that \(n/k\) is a natural number.
2. Prove that for every number \(x\), if \(x^2\) is irrational then \(x\) must also be irrational.
3. True or False? If \(b\) is irrational, then \(\frac{b}{b^2+1}\) is also irrational. Prove or disprove.
4. Let \(F_n\) be the \(n\)-th Fibonacci number, starting with \(F_0=0\) and \(F_1=1\) (and so \(F_2=1\)). First verify numerically by examining the first 6 cases, and then prove by mathematical induction, that for every \(n\geq 1\) we have the formula: \[F_1^2 + F_2^2 +\cdots + F_n^2 = F_n F_{n+1}\]
5. The Lucas numbers are generated by starting with \(L_0 = 2\), \(L_1=1\) and for each subsequent \(n\) we have \(L_n = L_{n-1} + L_{n-2}\). So same recursive relation as the Fibonacci numbers, but different starting numbers. Compute the first 10 Lucas numbers. Prove by mathematical induction that the Lucas numbers and the Fibonacci numbers have the relation \(L_n = F_{n-1} + F_{n+1}\), for \(n\geq 1\).