You are being asked to submit soundly reasoned and well written proofs by induct

Question

You are being asked to submit soundly reasoned and well written proofs by induction. This means the solution to each question must include:

1. A clear statement of the inductive hypothesis

2. The validation of the base case(s): proving the inductive hypothesis hold for some concrete value or instance

3. A clear explanation of the inductive step: how the inductive hypothesis was applied to derive the property for the next case

4. An demonstration that the inductive step establishes the inductive hypothesis holds for the next case.

___________________________________________________________________________________________________________________________________________________

Your answer must include a clear explanation of the steps involved in the proof: it is not sufficient to just turn in a series of equations without a description or motivating explanation for each step.

__________________________________________________________________________________________________________________________________________________

Question 1

In class, we defined a full binary tree to be first: binary, i.e. a tree where every node has at most two children, labelled as rightand left; and second: full, meaning each node either has no children, or a full complement of two. Furthermore, we call nodes with no children leaves, and nodes with any children internal nodes. So, another way to define a full binary tree would be: "a binary tree where every internal node has exactly two children."

We can extend this to define full ternary trees, which are trees where every node can have up to three children, and being full, every internal node has exactly 3 children.

Let intNodes(T) denote the number of internal nodes in a full ternary tree T, and let leaves(T) denote the number of leaves in that tree. Prove by induction that for all full ternary trees:

    leaves(T) = 2 * intNodes(T) + 1

Explanation / Answer

Basis: Consider a ternary tree with 1 internal node. By defination of ternary tree it will have 0 child or 3 children.

so, if it has 0 child, so the single node will be leaf node and no internal node, i.e. leaves=1=2*0+1.

And if it has 3 children then, it will have 1 internal node and 3 leaves. i.e. leaves=3=2*1+1=2*intNodes+1.

Thus basis holds in both cases.

Inductive hypothesis:

Assume a ternary tree with k internal nodes has 2k+1 leaves.

Inductive step:

Now consider a ternary tree with (k+1) internal nodes, it is built by adding 3 nodes to a leaf node on a k internal node ternary tree..

Thus a leaf node becomes a inter node and 3 leaf nodes are added to previous ternary tree.

i.e. Number of leaves deducted by 1 and added by 3

So, Number of leaves of (k+1) internal node ternary tree

=number of leaves of k internal node ternary tree -1+3

=2k+1-1+3

=2k+3

=2(k+1)+1

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.