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.