Algorithm: How to find the number of independent sets in a tree?
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) &amp; = &amp; \prod_{m \in Adj[n]}B(m) \\
B(n) &amp; = &amp; \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.