I have such a hard time doing this sort of thing that it's annoying me. I'm not very mathematically inclined but it frustrates me that a solution with such a small answer takes me more than a page to figure out and at times I HAVE to look up the answer. For example for the following question:
$11^n - 4^n$ is always divisible by 7
Here is how I did it and I most likely made a mistake somewhere along the way too:
base case: 1
$11^1 -4^1 = 7$ so it holds true
let n $\in \mathbb{N}$, Assume $11^n - 4^n$ is divisible by 7. (Induction hypothesis)
$11^{n+1} -4^{n+1}$ = $11^n(11) - 4^n(4)$
=$11^n(10+1) - 4^n(3+1)$ #this here is just me basically hoping that it works out
= $11^n(10) +11^n - 3(4^n) - 4^n$
= $11^n(10) - 3(4^n) + (11^n - 4^n)$
since we know $(11^n - 4^n)$ by the I.H, figure if $11^n(10) - 3(4^n)$ is divisible by 7
$11^n(10) - 3(4^n)$ = $11^n(10) - (2+1)(4^n)$ #again this is me trying something random and hoping it works
= $11^n(10) - 2(4^n) - 4^n$
= $11^n(10) - (10-8)(4^n) - 4^n$
= $11^n(10) -10(4^n) + 8(4^n) - 4^n$
ok so looks like midway into looking at my answer to this question i found a mistake...every question like this i always end up going in circles or go nowhere.. is there some sort of trick to see just WHAT i'm suppose to change in the equation to get a result which satisfies the claim?
you are trying to end up with a term that is divisible by 7 and a term that contains $11^n-4^n$.
Write $11^{n+1}-4^{n+1} = 11 \cdot 11^n - 4 \cdot 4^n = 7 \cdot 11^n + 4 \cdot 11^n - 4 \cdot 4^n = 7 \cdot 11^n + 4 \cdot (11^n - 4^n )$.