Proving a Recursive Formula

Question

I know there are some questions on this site about how to find a recursive formula, but I've already found the formula. I'm doing an assignment (http://mathstat.dal.ca/~svenjah/math2112/Assign6.pdf) where we have to find and then prove a recursive formula for a sequence. The sequence is defined as such:

"Consider a row of n squares. You want to fill this row with round tokens (taking up one square) and dominoes (taking up two adjacent squares). Let a_n be the number of ways to do this."

So, I have a recursive formula a_n = a_n-1 + a_n-2. Now, I have to "[prove] that my recursion is true."

How is this possible? Should I use a contradictory supposition (eg., that there is a lowest a_n for which the formula does not hold)? Is it even possible to prove a recursive formula?

Also, I shouldn't be proving it with an explicit formula, because I'm not yet supposed to have found the explicit formula.

Answer 1

You can prove it thus: The first square is either covered by a round token or by a domino. If it's covered by a round token, the remaining $n-1$ squares can be covered in $a_{n-1}$ ways. If it's covered by a domino, the remaining $n-2$ squares can be covered in $a_{n-2}$ ways. Together, that yields $a_n=a_{n-1}+a_{n-2}$.

Answer 2

For any way of filling a row of $m$ cells the last cell on the right either has a round token or a domino. If it has a token, other $m - 1$ cells can be filled in $a_{m - 1}$ ways. If it has a domino, other $m - 2$ cells can be filled in $a_{m-2}$ ways. Thus, $a_{m} = a_{m - 1} + a_{m - 2}$.

Edit: removed false claim of using mathematical induction.