Foros de matemática
23/10/2014, 04:55:44 am
 Bienvenido(a), Visitante. Por favor, ingresa o regístrate. 1 Hora 1 Día 1 Semana 1 Mes Siempre Ingresar con nombre de usuario, contraseña y duración de la sesión

 Páginas: [1]   Ir Abajo
 Autor Tema: function sum  (Leído 764 veces) 0 Usuarios y 1 Visitante están viendo este tema.
jacks
Pleno*

Karma: +0/-0

Sexo:
Indonesia

Mensajes: 269

 « : 25/04/2012, 04:22:06 pm »

consider a function   on non-negative integers such that

and   for

Then show that
 En línea
pabloN
Pleno*

Karma: +0/-0

Sexo:
Uruguay

Mensajes: 2.909

 « Respuesta #1 : 25/04/2012, 07:09:28 pm »

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 in the inductive step we asumme no more hypothesis than strictly necessary.
 En línea

Schindler's List by Nicola Benedetti
pabloN
Pleno*

Karma: +0/-0

Sexo:
Uruguay

Mensajes: 2.909

 « Respuesta #2 : 26/04/2012, 10:08:29 am »

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)-
 En línea

Schindler's List by Nicola Benedetti
jacks
Pleno*

Karma: +0/-0

Sexo:
Indonesia

Mensajes: 269

 « Respuesta #3 : 27/04/2012, 09:36:37 am »

Thanks Pablon
 En línea
jacks
Pleno*

Karma: +0/-0

Sexo:
Indonesia

Mensajes: 269

 « Respuesta #4 : 29/04/2012, 11:15:36 pm »

Answer given in book is like this way:

So

But I did not understand second line.

Thanks.
 En línea
pabloN
Pleno*

Karma: +0/-0

Sexo:
Uruguay

Mensajes: 2.909

 « Respuesta #5 : 17/07/2013, 01:20:02 am »

Hello, jacks.

Answer given in book is like this way:

So

But I did not understand second line.

You did not understand the second line because the first one is wrong  . It should be:

Applying repeatedly equation , we obtain

Now dividing by

This implies that

Since , we have

as we wanted.
 En línea

Schindler's List by Nicola Benedetti
 Páginas: [1]   Ir Arriba
 « anterior próximo »
Ir a: