function sum

[jacks]

consider a function   on non-negative integers such that  

and   for

Then show that

[pabloN]

For simplicity, let us rename as for each . Then we have the following equations:



So we must prove the above recursion satisfies: . By induction on .

If the proposition holds trivially.

Now suppose that for all , . This is our induction hypothesis. In particular, we will asumme that it is true when and (*). We want to show the proposition also holds when . Claim:

Note that:



But . So 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 .

Regards.

(*) 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 the in the inductive step we asumme no more hypothesis than strictly necessary.

[pabloN]

If the proposition holds trivially.

Now suppose that for all , . This is our induction hypothesis. In particular, we will asumme that it is true when and

Sorry, I've made a mistake again . This is not correct because when we would be assuming that the affirmation is true when and and that doesn't make sense since the property is referred to positive integers.

The right proof is suggested here:

Let be a property, then holds for all if:

i)-

ii)-

[jacks]

Thanks Pablon

[jacks]

Answer given in Book is Like this way



So

But I did not Understant Second line

Thanks