Correctness proof for finding weighted maximum independent set for a tree The maximum weighted independent set for a tree can found out using the following dynamic programming approach.

Min[u] = wt(u) + Σ Mout[v] where v ∈ children(u) Mout[u] = Σ max { Min[v], Mout[v] } where v ∈ children(u)

where Min[u] and Mout[u] computes the total weight of the maximum independent set for the sub tree rooted at u by including or excluding u respectively.

I tried to proof the correctness of this algorithm. Suppose the independent set ( say I ) generated from this algorithm is not of maximum weight. Let the maximum weighted independent be I'. Then there must be a vertex V'∈ I' and V' ∉ I. And also there can be 2 cases. Either parent(V')∈ I or parent(V') ∉ I. I tried both the cases to solve furthur but could not proceed. Is this approach correct or there is some alternative way to prove the correctness.
Here is an easier-to-understand dynamic programming approach. I think if you can prove this, then you can prove yours.

Let $\textsf{I}(u)$ be the weight of the weighted largest independent set of subtree rooted at $u$.

The goal is to compute $\textsf{I}(r)$, where $r$ is the root of the tree.

The recurrence relation for dynamic programming is:

$$\textsf{I}(u) = \max \{ w(u) + \sum_{v: \text{ grandchild of } u} I(v), \sum_{v: \text{ child of } u} I(v) \}$$

Can you prove (or disprove) it? 

Hint: Do a simple case-by-case analysis.