2
$\begingroup$

we got two inductive riddles for homework. I need a hint to get me started. So the first one is related to the Fibonacci numbers:

Let ‫‪Dn‬‬ be the number of possible ways to cover a table of size 2*n with domino bricks of size 2*1 (no overlapping), then ‫1+‪Dn = Fn‬‬. Prove using an induction

*‫1+‪Fn‬‬ is a Fibonacci number

The second riddle is:

I have a chocolate bar of n cubes and I break it to two smaller bars. I keep doing so until I have n separated chocolate cubes. Prove using a complete induction that the process will end after exactly n-1 "breaking steps"...

Like I said, this is homework so I only want a hint to point me in the right direction. Thanks a lot!

1 Answers 1

5

Chocolate first: How many pieces after $k$ steps? I don't see the need for "complete" induction.

For the tiling problem, start tiling from the left. Either you use a domino "vertically," then do the rest, or you use two dominoes "horizontally," then do the rest. That should give you the familiar recurrence. The initial values $D_1$ and $D_2$ are easily computed. By induction, two sequences that satisfy the same recurrence and the same initial conditions are the same.

Remark: For the $0\times 2$ table, there is $1$ way to tile (do nothing). So in a sense we get the full Fibonacci sequence. (If the table of width $0$ bothers you, forget about this remark.)