Prove that for every integer n, the number En = 5^n + 2*3^(n-1) +1 is a multiple of 8.
I tried to use induction, but I was told that a more simple way of doing it was using the rules of divisibility by 8.
Any ideas?
Sorry... Typo! I meant for positive integers.
?
Favorite Answer
Clearly, it's not true for every integer, because for 0 or negative integers the powers of 5 and 3 result in a fractional value. So let's start by assuming that we're only proving this for POSITIVE integers.
The powers of 5 are
5, 25, 125, 625, ...
Look closely, and you'll see a pattern in the remainders if they're divided by 8:
5, 1, 5, 1, and so forth. 5 taken to any odd positive power is equal to
8j+5 for some integer j, so the next even power would be
5 (8j+ 5) = 40j + 25 = 8k + 1 where k=5j+3, and the next odd power would be
5 (8k + 1) = 40k + 5 = 8m + 5 where m=5k.
This sort of arithmetic using remainders only is called modulus arithmetic. [Maybe you already know about it, but I'm not taking chances here.] In standard notation, we can say that
5^n = 5 (mod 8) for any odd positive integer n, and
5^n = 1 (mod 8) for any even positive integer n.
The powers of 3, starting with the 0 power (because we need to deal with the (n-1)th power), are
1, 3, 9, 27, ...
and we get the same sort of pattern:
3^n = 3 (mod 8) if n is an odd positive integers, and
3^n = 1 (mod 8) if n is an even positive integer.
Now, for any positive integer n, the expression
5^n + 2 * 3^(n-1) + 1
works out to
5 + 2*1 + 1 = 8 (mod 8) if n is odd, and
1 + 2*3 + 1 = 8 (mod 8) if n is even.
Either way, the remainders when divided by 8 add up in such a way that the whole expression is always divisible by 8.