# Thread: Prove each of the following by induction

1. ## Prove each of the following by induction

As the title says, prove each of the following by induction:

a) $\displaystyle \sum_{j=1}^nj2^j=(n-1)2^{n+1}+2$ for every positive integer $\displaystyle n$

b) $\displaystyle 4^n<n!$ for all integers $\displaystyle n>8$

c) $\displaystyle n^2-10n+8$ is positive for all $\displaystyle n\geq10$

d) $\displaystyle 3$ divides $\displaystyle n^3+2n$ for all positive integers $\displaystyle n$

2. Hello Runty
Originally Posted by Runty
As the title says, prove each of the following by induction:

a) $\displaystyle \sum_{j=1}^nj2^j=(n-1)2^{n+1}+2$ for every positive integer $\displaystyle n$

b) $\displaystyle 4^n<n!$ for all integers $\displaystyle n>8$

c) $\displaystyle n^2-10n+8$ is positive for all $\displaystyle n\geq10$

d) $\displaystyle 3$ divides $\displaystyle n^3+2n$ for all positive integers $\displaystyle n$

I'll leave all the peripheral bits of the proofs to you. But here are the algebraic proofs that $\displaystyle P(n) \Rightarrow P(n+1)$.

a) $\displaystyle P(n)$ is the propositional function: $\displaystyle \sum_{j=1}^nj2^j=(n-1)2^{n+1}+2$

Then $\displaystyle P(n)$
$\displaystyle \Rightarrow \sum_{j=1}^{n+1}j2^j=(n-1)2^{n+1}+2+(n+1)2^{n+1}$
$\displaystyle =2n.2^{n+1}+2$

$\displaystyle =([n+1]-1)2^{[n+1]+1}+2$
$\displaystyle \Rightarrow P(n+1)$
b) $\displaystyle P(n)$ is the propositional function: $\displaystyle 4^n<n!$

Then $\displaystyle P(n)$
$\displaystyle \Rightarrow 4^{n+1}<4.n!$
$\displaystyle <(n+1).n!$ for $\displaystyle n>8$

$\displaystyle <(n+1)!$
$\displaystyle \Rightarrow P(n+1)$
c) $\displaystyle P(n)$ is the propositional function:$\displaystyle n^2-10n+8 > 0$

Now $\displaystyle (n+1)^2 -10(n+1) +8=n^2 -8n -1$
$\displaystyle =n^2-10n+8 +2n -9$
$\displaystyle > n^2-10n+8$ since $\displaystyle 2n-9>0$ when $\displaystyle n \ge 10$
Hence $\displaystyle P(n) \Rightarrow (n+1)^2 -10(n+1) +8>0$
$\displaystyle \Rightarrow P(n+1)$
d) I'll leave this to you. It's rather similar to (c).

Expand and simplify $\displaystyle (n+1)^3 + 2(n+1)$. Then express the resulting expression in the form $\displaystyle n^3 + 2n + f(n)$, and you'll find that $\displaystyle f(n)$ is divisible by $\displaystyle 3$.

Can you fill in all the gaps?