How to prove that the fraction is integer by mathematical induction?

Question

How can I prove that the fraction

$$P(n) = \frac{1}{60} (7 * 4^n - 42 * (-1)^n - 10) $$

is integer for all natural numbers by mathematical induction method?

I tried to find the difference between $P(k + 1)$ and $P(k)$, but could not transform it to the original fraction.

Show that $60$ divides the expression by induction. Did you try already $n=1$? The induction has been done several times here, in several variations, see for example here. — Dietrich Burde, Mar 17, 2018 at 19:09
Write $P(n)=Q(n)/60.$ Show that $Q(n+1)-Q(n)$ is divisible by $60$. — saulspatz, Mar 17, 2018 at 19:14
Hint. it may be easier to use the difference $P(k+2) - P(k)$. — Malcolm, Mar 17, 2018 at 19:20

velut luna · Accepted Answer · 2018-03-26 23:15:08Z

6

$$P(1)=\frac{1}{60}\left(28+42-10\right)=1$$ $$P(2)=\frac{1}{60}\left(112-42-10\right)=1$$ $$P(k+2)-P(k)=\frac{4^k\times 105}{60}=7\times4^{k-1}$$

answered Mar 17, 2018 at 19:22

velut luna

9,6222 gold badges24 silver badges52 bronze badges

1

$\begingroup$ how is $4^k * 112$ divisible by $60$? $\endgroup$
– sku
Mar 26, 2018 at 16:34
$\begingroup$ @sku Sorry! Typo. Corrected. Thanks! $\endgroup$
– velut luna
Mar 26, 2018 at 23:20
$\begingroup$ Make it $7 * 4^{k-2}$ $\endgroup$
– sku
Mar 27, 2018 at 3:31

Add a comment |

1 Answer 1