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!