How to simlpify this Sum?

Question

I want a simplified form of:

$$\displaystyle N = \sum_{\displaystyle 0 \leq 2m \leq n} \binom {n}{2m} 2^{n-2m}.$$

Actual Question:

There is $ 1 \times n$ rectangle which is broken into $n$ unit squares. Now each square is coloured with either Red, Green, or Blue colours (not necessary that every colour appear in the squares). Let $f(n)$ denote the number of colourings in which Red colour occurs even number of times $(0,2,4,...)$.

What will be the value of $\displaystyle \frac {f(9)}{f(3)} ?$

My attempt:

$\displaystyle f(9) = \binom {9}{0} \times 2^{9} + \binom {9}{2} \times 2^{7} + \binom {9}{4} \times 2^{5} + \binom {9}{6} \times 2^{3} + \binom {9}{8} \times 2^{1}$

Similarly $f(3)$.

Thus I added the terms indivisually... that took a lot of time, then I tried to simplify the summation, but I was unsuccesful in doing so...

I would pefer a hint, not the answer.

Answer 1

The sum is equal to:

$$S={3^n+1 \over 2}$$

Answer 2

Use $$\sum_{k=0}^{n} {n \choose 2k} x^{2k}=\frac{(1+x)^n+(1-x)^n}{2}$$ $$M=\sum_{k=0}^{n} {n \choose 2k} 2^{n-2k}=2^n \frac{(1+1/2)^n+(1-1/2)^n}{2}=\frac{3^n+1}{2}.$$ When $2k>n$, the vinomial coeffiocient vanishes.