$1+4^n+7^n$ is divisible by $3$ for all $n \in \mathbb{N}$ 
Prove that $1+4^n+7^n$ is divisible by $3$ for all $n \in \mathbb{N}$.

I have to do it with induction. 
So I got my start, for $n=0$: We have $1+4^0+7^0 = 1+1+1 = 3$ and that's clearly divisible by $3$.
Then I have to do the induction, so I assume that $1+4^k+7^k$ is divisible by 3, and then look at $1+4^{k+1}+7^{k+1}$. Though I'm stuck here, I have to be able to write it like $1+4^k+7^k + \text{(something)}$ or $(1+4^k+7^k)*\text{(something)}$, I guess, but can't figure out what.
 A: Hint: $$(1+4^{k+1}+7^{k+1})-(1+4^k+7^k)=3\cdot 4^k+6\cdot 7^k.$$
To show this, note for example that $4^{k+1}-4^k=4^k(4-1)=3\cdot 4^k$. 
A: HINT:
Without induction:
For any integer $m,$
$$3m+1\equiv1\pmod3\implies (3m+1)^n\equiv1^n\equiv1$$
Now, $\displaystyle1=3\cdot0+1,4=1+?,7=1+?$

Induction:
If $f(m)=1+4^m+7^m,$
$\displaystyle f(m+1)-f(m)=4^m(4-1)+7^m(7-1)$
or $\displaystyle f(m+1)-7f(m)=1+4^{m+1}+7^{m+1}-7(1+4^m+7^m)=4^m(4-1)-6$
or $\displaystyle f(m+1)-4f(m)=\cdots$
In any case, $f(m+1)$  will be divisible by $3\iff f(m)$ is
Now establish the base case i.e., $m=1$  
A: Note that $1 + 4^n + 7^n = 1 + (3 + 1)^n + (6 + 1)^n$. Using the binomial Newton, the last terms of $(3 + 1)^n$ e $(6 + 1)^n$ ending in 1 for all $n \in \mathbb{N}$.Thus, as we will always rest 3, so that the given expression is divisible by 3.
A: Here is a different way of looking at it, which is more complex, but shows a more general idea.
If $A, B, C$ are fixed, any series of the form $f(m)=A\cdot 1^m+B\cdot 3^m+C\cdot 7^m$ satisfies a recurrence relation of the form (three terms on the right, because we are dealing with a sum involving three powers) $$f(m+3)=Qf(m+2)+Rf(m+1)+Sf(m) \dots (1)$$
You can get the coefficients by examining the polynomial (factors derived from powers above) $$(x-1)(x-4)(x-7)=x^3-12x^2+39x-28$$ whence $Q=12, R=-39, S=28$. If the powers were different, you would have different values. Equation $(1)$ then shows you that once you have three consecutive members of the series divisible by some number $N$, then every subsequent member of the sequence will also be divisible by $N$.
Every series defined as a sum of powers in this way satisfies a linear recurrence. So it is possible to show in quite general terms that divisibility persists once it is established. None of the steps is hard to prove, but in any specific case direct manipulation of the terms is likely to furnish a reasonably straightforward specific proof.
A: Other people have answered, but since you are asking for tips about induction and how to find the inspiration to solve it... This is how I'd try to solve it if I had no idea where it was heading.
I have $1 +4^{k+1} + 7^{k+1}$ and I want to express it in terms of $1+4^{k} + 7^k$.  Well, the only thing I see at first is $4^{k+1} = 4^k*4$ and the same for 7.  So I try it and see where it goes.
$1 + 4^k*4 + 7^k*7$.
Okay, that's close but the pesky extra terms are in the way.  That $4^k*4$ is too big with that extra 4.  I want to reduce to multiples of 3.  Can I break this down in terms of multiples of 3 while keeping the $4^k$ but mucking around with the four to get it in terms of 3?
Well, 4 = 3+1, so $1 + 4^k*4 = 1 + 4^k(3 + 1) = 1 + 4^k*3 + 4^k$. Good. I've got the $4^k$ isolated!  I've added an extra $3*4^k$ but that's okay as it's a multiple of 3.
Let's do the same thing with the $7^k*7$.  7 = 2*3 + 1.  So
$1+4^k*4 + 7^k*7 = 1 + 4^k(3 + 1) + 7^k(2*3 + 1) = 1 + 3*4^k + 4^k + 2*3*7^k + 7^k = 1 + 4^k + 7^k + 3*4^k + 2*3*7^k$.
Now that extra mess is just a bunch of multiples of 3s.
$1+4^k*4 + 7^k*7 =1 + 4^k + 7^k + 3*4^k + 2*3*7^k = (1 + 4^k + 7^k) + 3*(4^k + 2*7^k)$.
And that's it.
