Foros de matemática
24/05/2016, 06:49:09 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

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

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Indonesia Indonesia

Mensajes: 340


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

consider a function [texx]f(x)[/texx]  on non-negative integers such that [texx]f(0)=1\;\;, f(1)=0[/texx] 

and [texx]f(n) + f(n-1) = nf(n-1) + (n-1)f(n-2)[/texx]  for [texx]n\geq 2[/texx]

Then show that [texx]\displaystyle \frac{f(n)}{n!} = \sum_{k=0}^{n}{\frac{(-1)^{k}}{k!}[/texx]
En línea
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.175


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

For simplicity, let us rename [texx]f(n)[/texx] as [texx]d_n[/texx] for each [texx]n\in \mathbb{N}[/texx]. Then we have the following equations:

[texx]\left\{\begin{array}{l}d_0=1\\d_1=0\\d_n=(n-1)(d_{n-1}+d_{n-2})\end{array}[/texx]

So we must prove the above recursion satisfies: [texx]\displaystyle d_n=n! \sum_{k=0}^{n}{\frac{(-1)^{k}}{k!}[/texx]. By induction on [texx]n[/texx].

If [texx]n=0[/texx] the proposition holds trivially.

Now suppose that for all [texx]m<n[/texx], [texx]\displaystyle d_m=m!\sum_{k=0}^{m}{\frac{(-1)^{k}}{k!}[/texx]. This is our induction hypothesis. In particular, we will asumme that it is true when [texx]m=n-2[/texx] and [texx]m=n-1[/texx] (*). We want to show the proposition also holds when [texx]m=n[/texx]. Claim:

[texx]\displaystyle (n-1)\left((n-1)!\sum_{k=0}^{n-1}{\frac{(-1)^{k}}{k!}}+(n-2)!\sum_{k=0}^{n-2}{\frac{(-1)^{k}}{k!}}\right)=n! \sum_{k=0}^{n}{\frac{(-1)^{k}}{k!}}[/texx]

Note that:

[texx]\begin{align*} (n-1)\left( (n-1)!\sum_{k=0}^{n-1}{\frac{(-1)^{k}}{k!}}+(n-2)!\sum_{k=0}^{n-2}{\frac{(-1)^{k}}{k!}}\right)&= (n-1)\left((n-1)!\frac{(-1)^{n-1}}{(n-1)!}+\sum_{k=0}^{n-2}{\frac{(n-1)!(-1)^{k}}{k!}}+\sum_{k=0}^{n-2}{\frac{(n-2)!(-1)^{k}}{k!}}\right)\\ &= (n-1)\left((-1)^{n-1}+\sum_{k=0}^{n-2}\Big( \frac{(n-1)!(-1)^{k}}{k!}+\frac{(n-2)!(-1)^{k}}{k!}\Big)\right)\\&= (n-1)\left((-1)^{n-1}+\sum_{k=0}^{n-2}\Big( (n-1)\frac{(n-2)!(-1)^{k}}{k!}+\frac{(n-2)!(-1)^{k}}{k!}\Big)\right)\\ &= (n-1)\left((-1)^{n-1}+\sum_{k=0}^{n-2} n\frac{(n-2)!(-1)^{k}}{k!}\right)\\ &= (n-1)(-1)^{n-1}+\sum_{k=0}^{n-2} \frac{n!(-1)^{k}}{k!}\right) \end{align}[/texx]

But [texx]{\displaystyle \sum_{k=n-1}^{n}{\frac{n!(-1)^{k}}{k!}}=\frac{n!(-1)^{n-1}}{(n-1)!}+(-1)^n=n(-1)^{n-1}+(-1)^{n-1}(-1)=(n-1)(-1)^{n-1}}[/texx]. So [texx]\displaystyle d_n=n! \sum_{k=0}^{n}{\frac{(-1)^{k}}{k!}[/texx] as we want.

Alternatively, it is possible to give a combinatorial argument to demonstrate this formula based on [texx]d_n[/texx] represents the number of desarrangements of length [texx]n[/texx].

Regards.

(*) Maybe it would have been more suitable to use a variant of the strong induction principle, which says:

Let [texx]P[/texx] be a property, then [texx]P(n)[/texx] holds for all [texx]n\in \mathbb{N}[/texx] if:

i)- [texx]P(0),\;P(1)[/texx]

ii)- [texx]P(n-2),\;P(n-1)\Longrightarrow P(n)[/texx]

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

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.175


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

If [texx]n=0[/texx] the proposition holds trivially.

Now suppose that for all [texx]m<n[/texx], [texx]\displaystyle d_m=m!\sum_{k=0}^{m}{\frac{(-1)^{k}}{k!}[/texx]. This is our induction hypothesis. In particular, we will asumme that it is true when [texx]m=n-2[/texx] and [texx]m=n-1[/texx]

Sorry, I've made a mistake again :llorando:. This is not correct because when [texx]n=1[/texx] we would be assuming that the affirmation is true when [texx]m=0[/texx] and [texx]m=-1[/texx] and that doesn't make sense since the property is referred to positive integers.

The right proof is suggested here:

Let [texx]P[/texx] be a property, then [texx]P(n)[/texx] holds for all [texx]n\in \mathbb{N}[/texx] if:

i)- [texx]P(0),\;P(1)[/texx]

ii)- [texx]P(n-2),\;P(n-1)\Longrightarrow P(n)[/texx]
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
jacks
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Indonesia Indonesia

Mensajes: 340


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: 340


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

Answer given in book is like this way:

[texx]f(n)-f(n-1) = -\left[f(n-1)-(n-1)f(n-2)\right][/texx]

So [texx]\displaystyle \frac{f(n)}{n!}-\frac{f(n-1)}{(n-1)!} = \frac{(-1)^n}{n!}[/texx]

But I did not understand second line.

Thanks.
En línea
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.175


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

Hello, jacks.

Answer given in book is like this way:

[texx]f(n)-f(n-1) = -\left[f(n-1)-(n-1)f(n-2)\right][/texx]

So [texx]\displaystyle \frac{f(n)}{n!}-\frac{f(n-1)}{(n-1)!} = \frac{(-1)^n}{n!}[/texx]

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:

[texx]\begin{equation}f(n)-{\red \mathbf{n}}f(n-1) = -\left[f(n-1)-(n-1)f(n-2)\right]\end{equation}[/texx]

Applying repeatedly equation [texx](1)[/texx], we obtain

[texx]{f(n)-nf(n-1)=(-1)^2\left[f(n-2)-(n-2)f(n-3)\right]=(-1)^3\left[f(n-3)-(n-3)f(n-4)\right]=\cdots=(-1)^{n-1}\left[f(1)-f(0)\right]=(-1)^n}[/texx]

Now dividing by [texx]n![/texx]

[texx]\dfrac{f(n)}{n!}-\dfrac{f(n-1)}{(n-1)!}=\dfrac{(-1)^n}{n!}\quad \Rightarrow \quad \dfrac{f(n)}{n!}=\dfrac{f(n-1)}{(n-1)!}+\dfrac{(-1)^n}{n!}[/texx]

This implies that

[texx]{\dfrac{f(n)}{n!}=\dfrac{f(n-1)}{(n-1)!}+\dfrac{(-1)^n}{n!}=\dfrac{f(n-2)}{(n-2)!}+\dfrac{(-1)^{n-1}}{(n-1)!}+\dfrac{(-1)^n}{n!}=\cdots=\dfrac{f(0)}{0!}+\dfrac{(-1)^1}{1!}+\dfrac{(-1)^2}{2!}+\cdots+\dfrac{(-1)^n}{n!}}[/texx]

Since [texx]f(0)=1=(-1)^0[/texx], we have

[texx]\displaystyle\frac{f(n)}{n!}=\sum_{k=0}^{n}{\frac{(-1)^{k}}{k!}[/texx]

as we wanted.
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
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!