Prove by induction of recurrence relation has solution

Assignment Help Basic Computer Science

Reference no: EM1348084

Q1) Kim has a great idea. He ?gures that if his classmates don't like red-black trees, then they may be more interested in his own new creation: wimpy-red-black trees, or WRB-trees for short. Kim has de?ned them similarly to red-black trees except that instead of requiring that:

"Every red node has both children black."
he requires that:

"No red node may have a red sibling or a red child."

Kim ?rst analyzes the most number of nodes M(k) that an WRB-tree can have if every path from the root to a leaf has k black internal nodes. He discovers that M(k) is de?ned by the recurrence relation:

M(0) = 0
M(k) = 2 + 3M(k - 1) for k > 0.

a. Describe why Kim's recurrence relation is correct.

b. Prove by induction that Kim's recurrence relation has solution: M(k) = 3^(k - 1)

Reference no: EM1348084

Questions Cloud

Accounting-management control systems : Jack's Outdoor World is the company which manufactures and sells garden furniture. They've been operating for past ten years and have the comfortable share of market.

Compute the radius of the path in the system : Two narrow slits 41 µm apart are illuminated with light of a wavelength 604 nm. What is the angle of the m=3 bright fringe in degrees.

Team motivation - emotional intelligence : Determine your current or former manager on each of the five components of emotional intelligence and can you apply the principles of emotional intelligence to your current situation?

Determining inspection cost : A company is considering additional final inspection costs of $1 per unit before delivery to customers. It currently delivers 60,000 units per year.

Prove by induction of recurrence relation has solution : Describe why Kim's recurrence relation is correct. Prove by induction that Kim's recurrence relation has solution: M(k) = 3^(k - 1).

Products have ingrained trademarks and trade names : Swimsuits for Women in FRANCE, Presume your company already markets and sells these products in the U.S. The products have ingrained trademarks and trade names.

Description of incentive plans : Description of incentive plans - select three different incentive plans, list the pros and cons for each plan.

Find out the lowest possible momentum for the particle : suppose that we could use the energy released when 5 g of antimatter annihilates 5g of matter to lift a mass 3 km from the Earth's surface. how much mass can we lift? answer in unites of kg.

Find the unit cost of euro for the us importer : A United State importer is planning about the appreciation of Euro against USD due to Euro payables of EUR 10,000,000 in three (3) months. To hedge the position, exporter wants to use futures markets.

User Account

All Pages