Prove the following statements using induction. Each proof needs to be complete, including the basis step and induction step; each step in your proof needs to be justified (except when it follows by simple algebra). 1. Prove that 1 +2+ + n = [n(n+1)/2]2 for every positive integer n. 2. Prove that 1 1!+2 2!+ n n! = (n+1)! - 1 for every positive integer n. 3. Prove that for every non-negative integer n, . .. 1+ 3 +5 +... + (2n + 1) = (n+1)(2n + 1) (2n + 3) 3 4. Prove that n + 2n is divisible by 3 for every positive integer n. 5. Show that you can pay any integer amount of money greater than $5 using only two- dollar and five-dollar bills. 6. Show that 3"