# Is this a valid weak induction proof on the number of branches in a tree? what would be a strong induction version?

The exercise goes as follows: prove by strong mathematical induction that for any tree $$T$$, if $$n$$ is the number of nodes and $$m$$ is the number of branches in $$T$$, then $$n = m + 1$$

I'm a beginner and haven't quite grasped the concept of strong induction so I tried my luck with weak induction first:

According to the property stated in the exercise then it must be the case that $$m = n - 1$$, so let $$P(n) = n = (n - 1) + 1$$ be the property we want to prove.

The base case is a tree with only one node and no branches so: $$P(1) = 1 = (1 - 1) + 1$$ which is true.

Let $$k$$ be any arbitrary positive integer to formulate the inductive hypothesis: $$P(k) = k = (k - 1) + 1$$

Assuming the inductive hypothesis as true, let us prove the case for $$k + 1$$ to prove the theorem: $$P(k + 1) = (k + 1) = [(k + 1) - 1] + 1$$

By the inductive hypothesis: $$P(k + 1) = [(k - 1) + 1] + 1 = [(k +1) - 1] + 1$$

$$= P(k + 1) = k + 1 = k + 1$$

Now my question is if this proof is correct in the first place since it seems a bit redundant (?) and how could I make this proof in a strong induction style. I know I'm supposed to assume that all cases up to $$k$$ are correct to do strong induction, but I only sort of understand it for sequences and this leaves me hanging a bit.

• You don't need induction to prove that $n=(n-1)+1$. That isn't what you need to prove. Where did $m$ get lost? – saulspatz Sep 13 '19 at 19:55

An important part of any induction proof is to be very clear what the proposition is! In this case, P(n) is the proposition that a tree with $$n$$ nodes has $$n-1$$ branches.

Your proof that P(1) holds is fine. So we now wish to prove P(k+1).

There's no need to be wary of strong induction. It allows you to assume that P(i) is true for every $$i\le k$$ and not just that $$P(k)$$ is true.It gives you more to work with!

OK. So we have a tree with $$k+1$$ nodes and we know that our proposition holds for all trees with fewer nodes. We need to find some smaller trees that we can use.

Let's take a branch of our tree and remove it. Because we had a tree (which has no cycles) it will now be split into two smaller trees. Let's say that one has $$a$$ nodes and one $$b$$ nodes. Important - remember that $$a+b=k+1.$$

How many branches does the tree with $$a$$ nodes have? It must have $$a-1$$. The other small tree must have $$b-1$$.

See why we needed to use strong induction?

So, how many edges did our large tree have before we lopped a branch off? Can you see why it must have had $$(a-1)+(b-1)+1?$$ But this number of branches is $$a+b-1=(k+1)-1=k$$, just what we wanted!

• thank you, I think it is clearer for me now – MikeKatz45 Sep 14 '19 at 18:46