# Number - Proof By Induction

a - answer    s - solution    v - video    d - discussion

## Question 1

Prove by mathematical induction for $n\ge1$ and $n\in\mathbb{Z}^+$:

a) $1+2+3+4+\dotsb+n=\frac{n(n+1)}{2}$a s v d

b) $1+3+5+7+\dotsb+(2n-1)=n^2$a s v d

c) $1+4+7+10+\dotsb+(3n-2)=\frac{n(3n-1)}{2}$a s v d

d) $1^2+2^2+3^2+4^2+\dotsb+n^2=\frac{n(n+1)(2n+1)}{6}$a s v d

e) $2^1+2^2+2^3+2^4+\dotsb+2^n=2^{n+1}-2$a s v d

## Question 2

Prove by mathematical induction for $n\in\mathbb{Z}^+$:

a) $\sum_{x=1}^n x^3 = \frac{n^2{(n+1)}^2}{4}$a s v d

b) $\sum_{x=1}^n x(x+1) = \frac{n(n+1)(n+2)}{3}$a s v d

c) $\sum_{x=1}^n \frac{1}{x(x+1)} = \frac{n}{n+1}$a s v d

d) $\sum_{x=0}^n r^x = \frac{1-r^{n+1}}{1-r}$, $r\neq1$a s v d

e) $\sum_{x=0}^n ar^x = \frac{a(1-r^{n+1})}{1-r}$, $r\neq1$a s v d

## Question 3

Prove by mathematical induction:

a) $6^n+4$ is divisible by $5$ for all $n\ge0$ and $n\in\mathbb{Z}^+$a s v d

b) $8^n-1$ is divisible by $7$ for all $n\ge1$ and $n\in\mathbb{Z}^+$a s v d

c) $5^n-1$ is divisible by $4$ for all $n\ge0$ and $n\in\mathbb{Z}^+$a s v d

d) $n^3-7n+9$ is divisible by $3$ for all $n\ge0$ and $n\in\mathbb{Z}^+$a s v d

e) $8^n-3^n$ is divisible by $5$ for all $n\ge1$ and $n\in\mathbb{Z}^+$a s v d

f) $5^n+2\times11^n$ is divisible by $3$ for all $n\ge0$ and $n\in\mathbb{Z}^+$a s v d

## Question 4

Prove by mathematical induction:

a) $2^n>2n$ for all $n>2$ and $n\in\mathbb{Z}^+$a s v d

b) $2^n<3^n$ for $n\geq1$ and $n\in\mathbb{Z}^+$a s v d

c) $n!>2^n$ for $n\geq4$a s v d

d) $2^n>4n$ for $n\geq5$ and $n\in\mathbb{Z}^+$a s v d

e) $n^2\ge2n$ for $n>1$ and $n\in\mathbb{Z}^+$a s v d

f) $n^2<4^{n-1}$ for $n\geq3$ and $n\in\mathbb{Z}^+$a s v d

## Question 5

Prove:

a) $T_n=3^n-2$ if $T_{n+1}=3T_n+4$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$a s v d

b) $T_n=2^n-1$ if $T_n=2T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$a s v d

c) $T_n=\frac{5^n-1}{4}$ if $T_n=5T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$a s v d

d) $T_n=3^n-2^n$ if $T_{n+2}=5T_{n+1}-6T_n$, $T_1=1$, $T_2=5$ for all $n\ge3$ and $n\in\mathbb{Z}^+$a s v d

e) $T_n<4$ if $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$a s v d

## Question 6

Prove by mathematical induction:

a) For any positive integer $n$, $\frac{\mathrm{d}}{\mathrm{d}x}x^n=nx^{n-1}$a s v d

b) $x^n-y^n$  can be divided by $x-y$ for $n\geq1$, $x\ne y$ and $n\in\mathbb{Z}^+$a s v d