1. ## Proof By Induction

For my Linear Algebra class we have to do Proof By Induction problems. I got #1 and #2 on the first page and I got the whole second page. But what do you do on #3 and #4 on the first page? Images attached. Thanks you for your time - I appreciate it.

2. ## Problem 1

$
\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}
$

Base Case

$
\sum_{i=1}^{1} i^2 = 1^2 = 1 , \frac{1(1+1)(2*1+1)}{6} = \frac{6}{6} = 1
$

Assume k $\in$ S

$
\sum_{i=1}^{k} i^2 = \frac{n(n+1)(2n+1)}{6}
$

Prove k+1 $\in$ S

$
\sum_{i=1}^{k+1} i^2 = \frac{(k+1)(k+2)(2k+3)}{6} = \frac{(k+1)(2k^2+7K+6)}{6} = \frac{2k^3+9k^2+13k+6}{6}
$

$
\sum_{i=1}^{k+1} i^2 = \sum_{i=1}^{k} i^2 + (k+1)^2
$

$
\sum_{i=1}^{k+1} i^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = \frac{k(k+1)(2k+1)}{6} + k^2+2k+1
$

$
= \frac{(k^2+k)(2k+1)}{6} + \frac{6k^2+12k+6}{6} = \frac{2k^3+3k^2+k}{6} + \frac{6k^2+12k+6}{6}
$

$
= \frac{2k^3+9k^2+13k+6}{6}
$

3. For the 3rd one,

$1!<2^1$
$2!<2^2$
$3!<2^2$
$4!>2^4$

If $n!>2^n,\$ then $(n+1)!>2^{n+1}$

$(n+1)!=(n+1)n(n-1)(n-2)(n-3)... =(n+1)n!$

$(n+1)n!>2^{n+1}$ ?

$(n+1)n!>(2)2^n$ ?

As n+1>2 for n>2

$(n+1)!>2^{n+1}$ if $n!>2^n$

4. For 4,

$\sum_{i=0}^na^i=\frac{1-a^{n+1}}{1-a},\ a\ne1$

$n=0,\ a^0=\frac{1-a}{1-a}$

$n=1,\ a^0+a^1=\frac{1-a^2}{1-a}=\frac{(1-a)(1+a)}{1-a}=1+a$

If $\sum_{i=0}^na^i=\frac{1-a^{n+1}}{1-a}$ then $\sum_{i=0}^{n+1}a^i=\frac{1-a^{n+2}}{1-a}$

Proof

$\frac{1-a^{n+1}}{1-a}+a^{n+1}=\frac{1-a^{n+1}+(1-a)a^{n+1}}{1-a}$

$=\frac{1-a^{n+1}+a^{n+1}-a^{n+2}}{1-a}=\frac{1-a^{n+2}}{1-a}$

5. Finally,

1=1
1+3=4
1+3+5=9
1+3+5+7=16

$\sum_{i=1}^n2n-1=n^2$

Hence $\sum_{i=1}^n2(n+1)-1$ should $=(n+1)^2$

$\sum_{i=1}^n2n+1=n^2+2n+1$ ?

Proof

$\sum_{i=1}^n2n-1+[2(n+1)-1]=n^2+[2(n+1)-1]=n^2+2n+1$