Let $S$$=${$1,2,...,n$}. Let $T$ be a non-empty subset of $S$. We call $T$ to be good if the average of the elements of $T$ belongs to $S$. For example, let $n$$=$$10$. Then, {$1,2,3$} is a good subset, but {$1,2,4$} is not. We denote the number of good subsets of $S$ by $f(n)$. Show that $f(n)+n$ is even.
We were given this problem in our problem seminar . I tried to solve this by establishing some sort of recursion between $f(n+1)$ and $f(n)$ and then applying induction on $n$. But I failed. Please help me ,someone . I would be very thankful .