Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A tiler lays a triangle-shaped panel on a wall, one row at a time. Row has tiles, row has tiles, row has tiles, and in general row has tiles. The tiler claims that a panel of rows always uses exactly tiles.
Write the base case, the inductive hypothesis, the step and the conclusion as separate lines.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Given. Row has tiles. Claim : .
Step 1. Base case. For the panel has tiles and . So is true.
Step 2. Hypothesis. Assume for some : the first rows use tiles.
Step 3. The step. Row has tiles. So rows use tiles. This is .
Step 4. Conclusion. is true and implies for every , so by induction is true for every .
Step 5. Part (b). tiles.
Step 6. Part (c). gives , so rows.
Check. The first three rows use tiles, as the formula says.
Answer: (b) tiles; (c) rows.
Log in to join the discussion.
Loading…
To prove for every : check the base case ; assume for some ; show . Then write the conclusion: by induction, holds for every .