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.