Question

Show that an \({{\bf{S}}_{\bf{k}}}\)-tree has \({{\bf{2}}^{\bf{k}}}\) vertices and a unique vertex at level k. This vertex at level k is called the handle.

Short answer

The given statement is true. That is, \({S_k}\)-tree has \({2^k}\) vertices and it has a unique vertex at level k.

Step-by-step solution

General form

Principle of \({{\bf{S}}_{\bf{k}}}\)-trees:A rooted tree T is called an \({{\bf{S}}_{\bf{k}}}{\bf{ - tree}}\)if it satisfies this recursive definition.

It is an\({{\bf{S}}_0}\)-tree if it has one vertex. For\({\bf{k > 0}}\),T is an\({{\bf{S}}_{\bf{k}}}\)-tree if it can be built from two \({{\bf{S}}_{{\bf{k - 1}}}}\)-treesby making the root of one the root of the \({{\bf{S}}_{\bf{k}}}\)-tree and making the root of the other child of the root of the first \({{\bf{S}}_{{\bf{k - 1}}}}\)-tree.

Principle of Mathematical induction:To prove that \({\bf{P}}\left( {\bf{n}} \right)\)is true for all positive integers n, where\({\bf{P}}\left( {\bf{n}} \right)\) is a propositional function, we complete two steps:

Basis step:Verify that \({\bf{P}}\left( 1 \right)\)is true.

Inductive step: Show that the conditional statement\({\bf{P}}\left( {\bf{k}} \right) \to {\bf{P}}\left( {{\bf{k + 1}}} \right)\) is true for all positive integers k.

Proof of the statement

Given that, the vertex k is called as handle.

To prove:\({S_k}\)-tree has \({2^k}\) vertices and it has a unique vertex at level k.

Prove the above statement by induction.

Let \(P\left( n \right)\) be “\({S_n}\)-tree has \({2^n}\) vertices and it has a unique vertex at level n.”

Basis step:

Put \(n = 0\).

\({S_0}\)has exactly one vertex and \({2^0} = 1\). Moreover, the one vertex is at level 0.

Thus \(P\left( 0 \right)\) is true.

Inductive step:

Let \(P\left( k \right)\)be true, thus \({S_k}\)-tree has \({2^k}\) vertices and it has a unique vertex at level k.

Itneeds to prove that \(P\left( {k + 1} \right)\)is true.

Since\({S_{k + 1}}\) consists of two copies of\({S_k}\), \({S_{k + 1}}\) contains twice as many vertices as \({S_k}\) and thus \({S_{k + 1}}\) has \(2*{2^k} = {2^{k + 1}}\) vertices.

Moreover, the only vertices at level \(k + 1\) are the vertices at level k in one copy of

\({S_k}\), which is 1.

Thus \(P\left( {k + 1} \right)\)is true.

Therefore, \({S_k}\)-tree has \({2^k}\) vertices and it has a unique vertex at level k.

Hence proved.