Teach the rote memorization but explain why it is true in terms of some understanding.

Yes, but this only really works if, when the student is presented with an example they didn't memorize, they can still solve it using their understanding. And to make sure they do understand, after they've practiced on the simple cases they can memorize, you routinely set problems that require understanding.

You can't start with understanding because when solving a few simple cases (like 5x5), memorization really is effective, and students may choose to memorize even if you don't explicitly tell them to.