FSA---a machine to determine a language

I find it's interesting to use FSA (Finite State Automata) to determine whether an expression belongs to the language. There are five important elements for each FSA: the set of all states,
a finite alphabet, transition functions, initial state and the set of accepting states. When I have an expression, I begins with the initial state and then, I look over the first character in the expression and go to the next state according to the transition function. After that, I look over the next character in the expression and go one state further. By the time that I have checked all characters in the expression, if I am in an accepting state, the expression belongs to the language and if it is not, the expression does not belong to the language denoted by the FSA.

Problem solving episode---WalkTilings(3)

I have shown that f(1) = 1, f(2) = 2, f(n) = f(n-1) + f(n-2) for n >= 3. So it seems that the solution is a sequence of Fabonacci numbers with f(n) = F(n+1), where F is Fabonacci numbers. Now I will prove this using complete induction.

Case1: When n = 1, f(1) = 1 = F(2).
Case2: When n = 2, f(2) = 2 = F(3).
Case3: When n >=3, suppose f(n-1) and f(n-2) and ... and f(1) is true. f(n) = f(n-1) + f(n-2) = F(n) + F(n-1) = F(n+1). So f(n) is true.

Conclude: for any natural number n >=1, f(n) = F(n+1).

Problem solving episode---WalkTilings(2)

I have shown the solution for the problem when n is small(from 1 to 5). Now I will find out the relationship between n and n + 1, beginning from small n. Suppose the solution for n is f(n).

How to get the solution for n = 3 from n = 2? My idea is that first put a tile in the leftmost 2*1 rectangle, then for the left 2*2 rectangle, I have 2 choices to put tiles, which is the solution for n = 2. Then I expand the leftmost 2*1 rectangle to the leftmost 2*2 rectangle. I have two choices to put tiles in this rectangle, but to avoid duplicates, I can only tile this one with two horizontal 2*1 tiles. So in total, there are 3 choices, 3 = 2 + 1 = f(2) + f(1).

Now consider n = 4. First, put a tile in the leftmost 2*1 rectangle, then for the left 2*3 rectangle, I have f(3) choices. Expand the leftmost 2*1 rectangle to the leftmost 2*2 rectangle. Still, to avoid duplicates, the 2*2 rectangle can only be tiled with two horizontal 2*1 tiles. For the left 2*2 rectangle, I have f(2) choices. Expand again the 2*2 rectangle to 2*3 rectangle. Though I have f(3) choices to tile this rectangle, each of them is identical to a way I put tiles before. So in total, f(4) = f(3) + f(2).

For n = 5, I still need to consider only two situations: when the leftmost rectangle is 2*1 and when the leftmost rectangle is 2*2. Then I get f(5) = f(4) + f(3).

But why is it true? I find out that when the leftmost rectangle is 2*2, the way I put two vertical tiles in it has occured in the previous step when the leftmost rectangle is 2*1. So I can only put two horizontal tiles in the 2*2 rectangle. When the leftmost rectangle is 2*3, all choices that I arrange tiles in it have occured in previous two steps. For rectangles of 2*4, 2*5,.., 2*(n-1), all choices that I arrange tiles in them have occured in the first two steps. So for any natural number n >=3, I just need to consider two situations: when the leftmost rectangle is 2*1, in which case the choices are f(n-1) and when the leftmost rectangle is 2*2, in which case the choices are f(n-2). So in total, f(n) = f(n-1) + f(n-2).

Problem solving episode---WalkTilings(1)

Here is the problem I am going to solve. It's called WalkTilings Problem.

Suppose you have tiles that are 1x2 rectangles, and you have to tile a walk that is 2x3 units long. You've got three choices: 3 vertical tiles, 1 vertical tile followed by two horizontal tiles, or two horizontal tiles followed by one vertical tiles.
How many choices do you have in tiling a 2x4 walk? How about a 2xn walk, where n is some natural number? Do you have a procedure that works for any n?

Here is the plan I want to work on.
Since it is hard to find out the solution when n is an abstract natural number at first, I will begin with the simplest condition(n = 1) and check several cases when n is small. I will investigate how the condition of n is related to the condition of n-1.

First, when n = 1, there is only one way to tile the walk.
When n = 2, there are two choices to tile the walk: 2 vertical tiles or 2 horizonal tiles.
When n = 3, there are three choices and they are presented in the problem.
When n = 4, there are 5 choices: 2 vertical tiles followed by 2 horizontal tiles, 4 vertical tiles, 1 vertical tile followed by 2 horizontal tiles and then followed by 1 vertical tile, 2 horizontal tiles followed by 2 vertical tiles, or 4 horizontal tiles.
When n = 5, there are 8 choices.

Proving the correctness of iteration and recursion

Basically, iteration and recursion are both loops. The difference is that recursion continues to call the function itself until it gets to a base case, while iteration has variables which change after each iteration.
Considering proofs of the correctness of iteration or recursion , I find out that it is easier to prove recursion by using complete induction. I assume P(1) and P(2) and ... and P(n-1) is true where n is a parameter about the function. Then I check that when the function calls itself, the parameter about the just called function is within the domain of (1, n-1) so that by assumption, the just called function returns the correct result.
As far as iteration is concerned, I need to have loop invariants which are true after each iteration. Loop invariants depends on the i-th iteration (i = 0, 1, 2,...), so the expression for loop invariants has parameter i. I need to prove the expression holds for every i using simple induction. Also, it's necessary to prove the iteration terminates. To prove that, I need to find an expression composed of loop invariants and prove it is a decreasing sequence so that the iteration terminates at last.