Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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.)

share|improve this answer
2  
+1 for "chocolate first" :-) –  Henning Makholm Nov 5 '11 at 18:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.