# Mathematical Induction in binary trees

• TheMathNoob
In summary, the proof shows that every 2-tree with n internal nodes has n+1 external nodes. The base case of n=1 has 1 internal node and 2 external nodes. In the inductive step, it is shown that for k internal nodes, there are k+1 external nodes. By adding an internal node, 1 external node is eliminated, resulting in a net change of +2 external nodes and +1 internal node. This demonstrates that for every additional internal node, there is an increase of 2 external nodes.
TheMathNoob

## Homework Statement

Show that every 2-tree(Definition 3.2) with n internal nodes has n+1 external nodes

## Homework Equations

A 2 tree is a tree which nodes have 2 children or no children.
Internal nodes are nodes which have two children
external nodes are leafs.

## The Attempt at a Solution

Proof
base case
n=1
Internal nodes=1
external nodes=2

Inductive step

Inductive hypothesis: Let k internal nodes have k+1 external nodes
so k+1 internal nodes will have (k+1)+1 external nodes.

TheMathNoob said:
so k+1 internal nodes will have (k+1)+1 external nodes.
What is your reason for thinking that that follows?

andrewkirk said:
What is your reason for thinking that that follows?
k internal nodes= k+1 external nodes. But I have been thinking and this doesn't make any sense.
1 internal node= 2 external nodes
so k+1 internal nodes= k+3 external nodes.

I know that when you add an internal node, you should eliminate one external node, but I don't know how to show that.

What happens to the internal and external node counts when you take an external node and give it two child nodes?

andrewkirk said:
What happens to the internal and external node counts when you take an external node and give it two child nodes?
+2 external nodes +1 internal nodes

Yes there are two new external nodes, but what is the net change in the number of external nodes?.

andrewkirk said:
Yes there are two new external nodes, but what is the net change in the number of external nodes?.
1?

## 1. What is mathematical induction in binary trees?

Mathematical induction in binary trees is a proof technique used to prove statements about binary trees. It involves breaking down a complex problem into smaller subproblems, and then proving the statement for the smallest subproblem. Next, the proof is extended to the next level of the tree, and this process is repeated until the entire tree is covered.

## 2. How is mathematical induction used in binary trees?

Mathematical induction is used in binary trees to prove statements about their properties or behavior. It allows us to prove these statements for a specific tree, and then generalize it to all trees of that structure. This is especially useful for proving properties of recursive algorithms on binary trees.

## 3. What are the steps involved in mathematical induction in binary trees?

The steps involved in mathematical induction in binary trees are as follows:

• Step 1: Prove the statement for the smallest binary tree (usually a single node).
• Step 2: Assume the statement is true for a binary tree with n nodes.
• Step 3: Prove that if the statement is true for a tree with n nodes, it is also true for a tree with n+1 nodes.
• Step 4: Conclude that the statement is true for all binary trees of that structure.

## 4. Can mathematical induction be used for any property of binary trees?

No, mathematical induction can only be used for properties that can be proved using a recursive approach. This means that the property must be true for a single node, and if it is true for a tree with n nodes, it must also be true for a tree with n+1 nodes.

## 5. What are some common mistakes to avoid when using mathematical induction in binary trees?

Some common mistakes to avoid when using mathematical induction in binary trees include:

• Not proving the statement for the smallest binary tree.
• Assuming the statement is true for a tree with n+1 nodes, without first proving it for a tree with n nodes.
• Not considering all possible cases when extending the proof to a tree with n+1 nodes.
• Using the wrong base case or making incorrect assumptions about the base case.

• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
11
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
• Engineering and Comp Sci Homework Help
Replies
10
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Engineering and Comp Sci Homework Help
Replies
15
Views
2K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Engineering and Comp Sci Homework Help
Replies
5
Views
2K
• Engineering and Comp Sci Homework Help
Replies
6
Views
2K
• Engineering and Comp Sci Homework Help
Replies
8
Views
1K