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.
Best Answer
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$.
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!