# 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) $\sum_{j=1}^nj2^j=(n-1)2^{n+1}+2$ for every positive integer $n$

b) $4^n for all integers $n>8$

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

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

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

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

b) $4^n for all integers $n>8$

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

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

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

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

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

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

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

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

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

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

Can you fill in all the gaps?