Foros de matemática
24/10/2014, 03:00:45 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.

Ingresar con nombre de usuario, contraseña y duración de la sesión
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: function sum  (Leído 767 veces)
0 Usuarios y 1 Visitante están viendo este tema.
jacks
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Indonesia Indonesia

Mensajes: 269


Ver Perfil
« : 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
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 2.909


Ver Perfil Email
« 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
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 2.909


Ver Perfil Email
« 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 :llorando:. 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
Desconectado Desconectado

Sexo: Masculino
Indonesia Indonesia

Mensajes: 269


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

Thanks Pablon
En línea
jacks
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Indonesia Indonesia

Mensajes: 269


Ver Perfil
« 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
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 2.909


Ver Perfil Email
« 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  :sonrisa_amplia:. 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
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.1 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!