For simplicity, let us rename
. Then we have the following equations:
So we must prove the above recursion satisfies:
. By induction on
the proposition holds trivially.
Now suppose that for all
. This is our induction hypothesis. In particular, we will asumme that it is true when
. We want to show the proposition also holds when
as we want.
Alternatively, it is possible to give a combinatorial argument to demonstrate this formula based on
represents the number of desarrangements of length
Maybe it would have been more suitable to use a variant of the strong induction principle, which says: Let be a property, then holds for all if:i)- ii)-
Note that if we use this theorem it is necessary to check two
base cases istead of only one. ¿What is the advantage? Certainly there is no advantage, but (from my modest point of view) is more elegant if in the inductive step we asumme no more hypothesis than strictly necessary.