number of subsets from the set {1,2,3,...,n} whose sum is even? I was told to do this using recursion (no loops and cannot be in constant n time). We essentially have a linked list starting at 1 going until n. I have figured out how to do this mathematically, but not recursively quite yet. The method being written takes an int as a parameter. Thanks for the help. 
 A: Let $n\geq1$. There are $2^{n-1}$ subsets  $A\subset\{2,3,\ldots, n\}$, and for each such $A$ exactly one of $A$ and $A\cup\{1\}$ has even weight. Since all subsets $\bar A\subset[n]$ are produced in this way exactly once the number of  $\bar A\in[n]$ with even weight is $2^{n-1}$.
A: Neither looping nor recursion is required. The sum of a set of integers is even if, and only if, the set contains an even number of odd numbers.
If recursion is required, you can use the standard idea that a subset of $\{1, \dots, n\}$ either contains $n$ or it doesn't. So the desired total is the number of even-sum subsets of $\{1, \dots, n-1\}$ plus the number of subsets $S$ of $\{1, \dots, n-1\}$ such that $S\cup\{n\}$ has even sum.
A: Let $S_n=\{1, 2, \ldots, n\}$. To make life simple, let us call the subsets with sum of elements even as even subsets and similarly, the subsets with sum of elements odd as odd subsets. 
Assume $e(n)$ and $o(n)$ as the number of even subsets and odd subsets respectively. 
Then, if $n+1$ is odd, every even subset of $S_{n+1}$ is EITHER even subset of $S_{n}$ OR odd subset of $S_{n}$ unioned with $\{n+1\}$. That is, if $n+1$ is odd, then $e(n+1) = e(n)+o(n)$. 
Similarly, if $n+1$ is even, every even subset of $S_{n+1}$ is EITHER even subset of $S_{n}$ OR even subset of $S_{n}$ unioned with $\{n+1\}$. That is, if $n+1$ is even, then $e(n+1) = 2e(n)$. 
So, we have a recursion:
$$
e(n+1) = \left\{\begin{array}{ll} e(n)+o(n) & \mbox{ odd } n+1\\
2e(n) & \mbox{ even } n+1\end{array}\right. 
$$
