If I haven't made a mistake then the first few values of your sequence look like this:
$$ (a_{m,n})=\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & ... \newline 1 & 1 & 2 & 3 & 5 & 8 & ... \newline 1 & 1 & 3 & 9 & 21 & 59 & \newline 1 & 1 & 4 & 21 & 91 & ... & \newline 1 & 1 & 5 & 41 & 329 & ... & \newline 1 & 1 & \vdots & \vdots & \vdots & & \newline \vdots & \vdots & & & & & \end{pmatrix} $$
Maybe the proposed induction gets easier if you look at the columns: It holds that $a(m,2)=a(m-1,2)+1$ for $m\geq 1$ and $a(0,2)=1$, thus $a(m,2)=m+1$, which is technically easier to deal with then Fibonacci, I guess.
