Foros de matemática
25/02/2017, 05:25:37 pm
 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 1415 veces) 0 Usuarios y 1 Visitante están viendo este tema.
jacks
Pleno*

Karma: +0/-0

Sexo:
Indonesia

Mensajes: 384

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

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

and $f(n) + f(n-1) = nf(n-1) + (n-1)f(n-2)$  for $n\geq 2$

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

Karma: +0/-0

Sexo:
Uruguay

Mensajes: 3.224

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

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

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

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

If $n=0$ the proposition holds trivially.

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

$\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!}}$

Note that:

\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}

But ${\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}}$. So $\displaystyle d_n=n! \sum_{k=0}^{n}{\frac{(-1)^{k}}{k!}$ as we want.

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

Regards.

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

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

i)- $P(0),\;P(1)$

ii)- $P(n-2),\;P(n-1)\Longrightarrow P(n)$

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
Pleno*

Karma: +0/-0

Sexo:
Uruguay

Mensajes: 3.224

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

If $n=0$ the proposition holds trivially.

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

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

The right proof is suggested here:

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

i)- $P(0),\;P(1)$

ii)- $P(n-2),\;P(n-1)\Longrightarrow P(n)$
 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

Sexo:
Indonesia

Mensajes: 384

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

Thanks Pablon
 En línea
jacks
Pleno*

Karma: +0/-0

Sexo:
Indonesia

Mensajes: 384

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

Answer given in book is like this way:

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

So $\displaystyle \frac{f(n)}{n!}-\frac{f(n-1)}{(n-1)!} = \frac{(-1)^n}{n!}$

But I did not understand second line.

Thanks.
 En línea
pierrot
pabloN
Pleno*

Karma: +0/-0

Sexo:
Uruguay

Mensajes: 3.224

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

Hello, jacks.

Answer given in book is like this way:

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

So $\displaystyle \frac{f(n)}{n!}-\frac{f(n-1)}{(n-1)!} = \frac{(-1)^n}{n!}$

But I did not understand second line.

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

$$$f(n)-{\red \mathbf{n}}f(n-1) = -\left[f(n-1)-(n-1)f(n-2)\right]$$$

Applying repeatedly equation $(1)$, we obtain

${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}$

Now dividing by $n!$

$\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!}$

This implies that

${\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!}}$

Since $f(0)=1=(-1)^0$, we have

$\displaystyle\frac{f(n)}{n!}=\sum_{k=0}^{n}{\frac{(-1)^{k}}{k!}$

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
 « anterior próximo »
Ir a: