1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – saulspatz Sep 13 '19 at 19:55
2
$\begingroup$

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!

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.