Olimpiada Grega

(Olimpíada Grega) Determine o número de funções f :{1, 2, ..., n } → {1995,1996} que satisfazem a condição
de que f (1) + f (2) +...+ f (n) é ímpar.

Resposta:2^(n-1)

Pelo que eu entendi, cada elemento de f pode ter dois resultados 1995 ou 1996, para que a expressão seja ímpar é necessário que haja a soma de um numero ímpar e outro numero par, logo o numero que antecede tem duas possibilidades, ser 1995 ou 1996, enquanto o numero sucessor pode ter apenas uma possibilidade que depende da escolha anterir  dessa ideia se usarmos o PFC:
2*1*2*1*2*1*2*1*2*1... que de forma geral podemos dizer que é (2^n)/2 - o que resulta em 2^(n-1). Só que eu achei essa resolução um pouco forçada demais e nem sei se esta certa podendo ser apenas uma coincidência.
Como resolvo?