I'm thinking that there are two cases for each sub-tree: the root is in the independent set and the root is not in the set. How to write a recursive algorithm for finding the number of independent sets in a tree? The tree is n-ary.
Algorithm: How to find the number of independent sets in a tree?
algorithms;graphs;trees
Let $T$ be the tree. For every $n\in T$, we indicate the number of independent sets in the subtree of $T$ rooted in $n$ that contain $n$ with $A(n)$, and the number of independent sets that do not contain $n$ with $B(n)$.The following recursive relations hold:$$\left \{\begin{array}{r c l}A(n) & = & \prod_{m \in Adj[n]}B(m) \\B(n) & = & \prod_{m \in Adj[n]}A(m) +B(m)\end{array}\right .$$Notice that we are using a constant number of memoization cells for each node of $T$. Interestingly enough, if $T$ is a line tree of $k$ nodes, the answer is exactly the $k$-th Fibonacci number.