Dn denotes the squares of a 2-by-n board using plain dominos. Then we see D1 = 1, D2= 2, and D3 = 3. find more values of Dn and guess an expression.

Question

I understand this problem that this sequence is a Fibonacci sequence. Also, Fibonacci series is f(n) = f(n-1) + f(n-2). However, I am stuck on how to prove this using strong induction.

I am at this step: Dk+1 = Dk + Dk-1. I do not where to go from here. Any help would be appreciated.