I will address your first question, but not the one for larger number of rods; as far as I know, it's still generally wide open what the optimal strategy might be even for $4$ rods and a smallish number of disks.
To show the optimal strategy for $n$ disks in $3$ rods is the "usual" one, you can do it by induction (which yields a recursive solution). I'm sure there are other ways of proving it, perhaps with Lucas numbers as you suggest.
Clearly, the optimal strategy with $n=1$ is to simply move the disk directly.
Assume you already have the optimal strategy for moving $k$ disks. To move $k+1$ disks, you need to move the largest disk from the initial rod to the terminal rod, but that is the only time it needs to move (it cannot help you with the other disks, since it must lie at the bottom at any given time, so any other moves only require further moves in the end); to move the bottom ($k+1$)st disk from the initial rod $I$ to the terminal rod $T$, you must first move the top $k$ disks out of the way; this requires moving the $k$ disks from the initial rod $I$ to the auxiliary rod $A$, and the optimal way of doing this is the optimal strategy you know for $k$ disks. Then you move the $k+1$st disk, and then you want to move the remaining $k$ disks from the auxiliary rod to the terminal one in as few moves as possible (the optimal way). So the optimal strategy for $k+1$ disks is to move the top $k$ using the optimal strategy for $k$ from $I$ to $A$, then move the largest disk from $I$ to $T$, then move the top $k$ disks using the optimal strategy for $k$ from $A$ to $T$.
By keeping track of the actual number of moves needed at each step, you can give the number. For $n=1$, the number is $1=2^1-1$. Assume that moving $k$ disks requires $2^k-1$ moves in the optimal strategy. The optimal strategy for $k+1$ described above takes $(2^k-1) + 1 + (2^k-1) = 2^k+2^k - 1 = 2^{k+1}-1$ steps; thus, the optimal solution for $n$ disks and $3$ rods requires $2^n-1$ moves.
(This does not generalize easily to more than $3$ rods for presumably obvious reasons).
A bit more interesting is trying to prove that the non-recursive solution gives an optimal solution; this solution only requires you to remember the last disk you moved at any given time (the recursive solution is more memory intensive, of course). Number the rods $0$, $1$, and $2$. We have three rules:
- Never move the same disk twice in succession.
- You can only move a disk from the top of one rod to the top of another rod.
- Moving a disk from rod $i$ to rod $j$ is only valid if $i\neq j$, and either rod $j$ is empty or the top disk in rod $j$ is larger than the top disk in rod $i$.
With these rules, the non-recursive algorithm has two simple steps:
- If you are moving the disk from rod $i$, and the two other rods are valid destinations, then move it to rod $i+1\mod 3$. Otherwise, move it to the only valid destination.
- If no move is possible, stop. Otherwise, continue.
This process will solve the puzzle with $3$ rods in the minimum number of moves.
While one might use mathematical thought to invent justifications about what symbol comes next, the major component of this puzzle is human perception. The viewer is the one who decides what features are important, and what things are meaningful.
You can contrast this type of puzzle with something like Sudoku, which really does reduce to a deterministic mathematical study. There isn't (supposed to be) any ambiguity about what comes next in those puzzles.
Pattern recognition is certainly important in mathematics, but actually I think it is more primitive because it relates to our perception and learning process. This indicates that you will get better, more interesting answers about solving such questions if you ask psychologists and/or machine learning experts.
Best Answer
This is all I can come up with:
1: Do the operation, the answer to that will be placed on the far right:
$ \begin{align} 7-3 &= 4 \\ 6 + 3 &=9 \\ 5-2 &= 3 \\ 11 + 2 &= 13 \end{align}$
2: Take the solution from above, multiply by the second digit in the original expression. Place it to the left of the answer we got in 1.:
$ \begin{align} 4\cdot 3 &= 12 \\ 9\cdot 3&=27 \\ 3\cdot 2&= 6 \\ 13 \cdot 2 &= 26 \end{align}$
So, we have
$ \begin{align} 124 \\ 279 \\ 63 \\ 2613 \end{align}$
3: If the original operation was addition, subtract, and vice versa. Stick this number to the left of the concatenated solutions to 1 and 2:
$ \begin{align} 7+3 &= 10 \\ 6 - 3 &=3 \\ 5+2 &= 7 \\ 11 - 2 &= 9 \end{align}$
Thus, we have
$ \begin{align} 10124 \\ 3279 \\ 763 \\ 92613 \end{align}$