And what do you think Maimonides thought—when he included reward and punishment in his principles of faith? Did he have a proof for it, or did he define the word “faith” differently? [Both options are a bit difficult for me.]

I have no idea. Maybe he thought there was a reliable tradition. Many think he writes esoterically, in which case there’s no way to know at all.

In the Torah portion of Bechukotai it is explicit that there is reward and punishment.
That is, God keeps account with His people and rewards them.
And since our own eyes see that many times the righteous get beaten down
while the wicked are doing great,
it follows that there must be a world of recompense where the wicked get beaten down and the righteous are doing great.
That follows logically, and I assume that once this is the premise it can also be derived from verses, and most likely there is an orderly tradition on the matter.