Last Problem Solving

We were handed the last problem sheet on Friday during lecture. It was about diagonals.

Understand the problem:

Suppose we have an m x n rectangular(m rows, n columns), then we draw a line from the upper left to the lower right corner. And the question is to find a formula to calculate how many squares the diagonal will meet.


Devise a plan:

1. Do a little analysis to avoid unnecessary work and to make sure every possible case will be covered. 
We found out that the case for an m x n rectangular and that for an n x m rectangular are the same. Thus, we can fix the number of rows or columns and change the other. We chose to fix the number of rows as m. Then for the number of columns, we start from m and add 1 to it every time. 

2. Start from small cases. Draw pictures and count.

3. Try to conclude something from the data we get. Make a guess for the formula.

4. Try to prove the formula works for every possible case.


Carry out the plan:

We started from small cases and counted the number of squares crossed in each case. 

During the process, we found out that the rectangular is symmetrical, so before we counted the number of squares, we drew a "middle point" in the rectangular, and we only needed to count the number of squares left above the point.

In some cases, when the number of columns in a rectangular is m plus an even number, and m is even (i.e. the rectangular has an even number of columns and rows), we can scale down to smaller rectangles.










Drawing the conclusion:

Suppose the rectangular has m rows and m+n columns(same cases if the rectangular has m columns and m+n rows).

Case1: n is even, m is even
for all k in natural numbers, n = 2k
then the number of squares met is 2(m + k - 1)

Case2: n is even, m is odd
for all k in natural numbers, n = 2k 
then the number of squares met is 2(m + k - 1) + 1

Case3: n is odd
for all k in natural numbers, n = 2k + 1
then the number of squares met is 2(m + k) 

This is so far I have figured out.


Problems to be solved:  

1. How to prove the formulas?
The first idea occurred to me is to prove by inductions. Assume the formula works when n = 2k, but I am right now stuck at how to prove that n = 2(k + 1) still works. 
I'd really appreciate it if someone could offer me a hint!

2. Since my examples are quite limited, I am not sure that the formulas I have concluded are correct.  
And I saw this kind of problem occurred on another student's post.
http://bryanlimycs.blogspot.ca/2014/11/week-11.html