Note that what we have to determine is only the parity of T_n.

Computing T_n, or using some recursion, do not seem to work.

Q: How could you decide if a set has an even or odd number of elements, without counting them?