Final answer:
Using mathematical induction, we proved the base case where a ternary tree of depth 0 has one leaf. We then assumed the proposition for depth k and proved it for depth k + 1, confirming the tree has 3^d leaves for any non-negative integer d.
Step-by-step explanation:
Proof by Induction
To prove that a ternary tree, denoted as t(d), has 3d leaf nodes for any non-negative integer d, we can use mathematical induction. The proof is done in two steps: the base case and the inductive step.
Base Case
For d = 0, a ternary tree with depth 0 is just a single node, which is also a leaf node. Hence, t(0) = 1 = 30, which satisfies the proposition.
Inductive Step
Assume the proposition is true for d = k, meaning t(k) = 3k.
For d = k + 1, a ternary tree of depth (k + 1) has one root node with three subtrees, each of depth k. By the induction hypothesis, each subtree will have 3k leaves. Therefore, the total number of leaves for the depth (k + 1) is 3 * 3k = 3k + 1. This completes the inductive step and thus proves that t(d) has 3d leaf nodes for any non-negative integer d.