Number of paths from root to a node in a tree

Question

How to prove inductively the total number of paths from the root to all leaves in a given tree?

From what I understand, one should show how to find the number of paths to a specific leaf, then use induction to find the total number of paths to all leaves. However, I am not quite sure how to show the this step mathematically.

Answer 1

1. Each leaf in a tree can be reached by exactly one path from the root node.

2. If there are $N$ leaves, there are $N$ paths from the root to a leaf node.

3. If there were more, there would be a leaf node with two paths to it. This contradicts Statement 1.

4. If there were fewer, there would be a leaf node with no paths to it, meaning it is not a leaf of the tree. This is a contradiction as well.

Therefore, the number of paths you're looking for is the number of leaves.