Prinzipiell kann man die Sache wie folgt angehen: Wir setzten erstmal einen konkreten Wert für \(m\) fest und schauen uns ein paar Werte für \(n\) an. Hoffentlich fällt uns dann ein System auf und wir können dann eine Vermutung formulieren, wie die explizite Form aussehen könnte. Und dann versuchen wir per Induktion zu beweisen, dass unsere Vermutung richtig ist.

Setzen wir also nun \(m=3\) fest. Dann erhalten wir die Werte: \(T_0 = 0\), \(T_1 = 1\), \(T_2 = 2\), \(T_3 = 1\), \(T_4 = 2\), \(T_5 = 3 \), \(T_6 = 2 \), \(T_7 = 3\), \(T_8 = 4\), \(T_9 = 3\).

Wenn man lange genug auf diese Werte schaut, dann kann man erkennen, dass für die Werte \( T_n = \lfloor \frac{n}{3}  \rfloor + (n \mod 3) \) gilt. Wenn wir hier die \(3\) durch das \(m\) ersetzen, erhalten wir unsere allgemeine Vermutung:

\(T_n = \lfloor \frac{n}{m} \rfloor + (n \mod m) \)

Dies zeigen wir jetzt durch Induktion über \(n\).

Induktionsanfang. Hier müssen wir aufgrund der Rekursionsformel etwas mehr zeigen als üblich. Wir müssen die Behauptung für alle \(n \in \{0, \dots, m-1\}\) zeigen. Sei also nun \(n \in \{0, \dots, m-1\}\) beliebig. Dann gilt

\(T_n = n = 0 + (n \mod m) = \lfloor \frac{n}{m} \rfloor + (n \mod m) \)

Damit ist der Induktionsanfang gezeigt.

Wir zeigen nun den Induktionsschritt. Sei \(n \ge m\). Als Induktionsannahme setzten wir voraus, dass bereits \(T_{n-m} = \lfloor \frac{n-m}{m} \rfloor + (n-m \mod m) = \lfloor \frac{n}{m} \rfloor - 1 + (n \mod m) \) gilt. Dann folgt auch

\(T_n = T_{n-m} +1 = \lfloor \frac{n}{m} \rfloor -1 + (n \mod m) + 1 = \lfloor \frac{n}{m} \rfloor + (n \mod m) \)

Damit ist auch der Induktionsschritt gezeigt.

Es gilt also tatsächlich die explizite Formel \(T_n = \lfloor \frac{n}{m} \rfloor + (n \mod m) \).