Use mathematical induction to prove that $(3^n+7^n)-2$ is divisible by 8 for all non-negative integers.

Question

Base step: $3^0 + 7^0 - 2 = 0$ and $8|0$

Suppose that $8|f(n)$, let's say $f(n)= (3^n+7^n)-2= 8k$

Then $f(n+1) = (3^{n+1}+7^{n+1})-2$

$(3*3^{n}+7*7^{n})-2$

This is the part I get stuck. Any help would be really appreciated.

Thanks.

Answer 1

Probably the easiest way to get it into the form you want is to do this

$$3(3^n)+3(7^n)+4(7^n)-6+4=3(3^n+7^n-2)+4(7^n+1)$$

Answer 2

$f(n)$ satisfies $f(n) = 11 f(n-1) - 31f(n-2) +21f(n-3)$

So by induction it's enough to check this is true for $n =0,1,2$.

Answer 3

If for $n=k, f(k)=3^k+7^k-2$

for $n=k+1,$

$\displaystyle f(k+1)-3f(k)= 3^{k+1}+7^{k+1}-2-3(3^k+7^k-2)$

$\displaystyle=7^k(7-3)+6-2=4(7^k+1)$ which is divisible by $8$ as $7^k$ is odd

So, $f(k+1)$ will be divisible by $8\iff f(k)$ is

We can start with $f(k+1)-7f(k)$ as well.