Primera prueba (MD 2)

1. (a) Probar que ∑_{k=0}^{n}(2 k + 1) = (n + 1)^{2}

Es la suma de n+1 términos de una progresión aritmética de razón 2, primer término 1 y último 2 n + 1

(b) Dada una función generatriz G(x) = ∑_{n≥0} g_{n} x^{n}, probar que

\frac{1}{(1 − x)} G(x) = ∑_{n≥0} (∑_{k≤n} g_{k}) x^{n}

Usar este hecho para probar que \frac{x+x^{2}}{(1−x)^{3}} es la función generatriz de la serie cuyo n-ésimo coeficiente es n^{2}

• \frac{1}{(1−x)^{2}} = 1 + 2x + 3x^{2} + 4x^{3} + 5x^{4} + ⋯

• \frac{x}{(1−x)^{2}} = x + 2x^{2} + 3x^{3} + 4x^{4} + ⋯ por lo tanto

• \frac{1+x}{(1−x)^{2}} = 1 + 3x + 5x^{2} + 7x^{3} + 9x^{4} + ⋯ y se tiene:

• \frac{x(1+x)}{(1−x)^{2}} = x + 3x^{2} + 5x^{3} + 7x^{4} + 9x^{5} + ⋯ = ∑_{n≥0}(2 n + 1)x^{n+1}

Si aplicamos ahora la fórmula \frac{1}{(1−x)} G(x) = ∑_{n≥0} (∑_{k≤n} g_{k}) x^{n}, se tiene,(en virtud del apartado a)) el resultado.

(c) Aplicando lo anterior, o de otro modo, encontrar la función generatriz de la serie cuyo n-ésimo coeficiente es (n + 1) (n − 1).

La serie con a_{n} = n^{2} −1 tendrá como función generatriz la de n^{2} ( es decir: \frac{x+x^{2}}{(1−x)^{3}} ) menos la de la sucesión

constante 1 (o sea \frac{1}{(1−x)} ), lo que da:

\frac{3x − 1}{(1 − x)^{3}}

Tener en cuenta la función generatriz: \frac{1}{(1−x)^{2}} = ∑_{n≥0} (n + 1) x^{n},

2. Describir el uso de las funciones generatrices para resolver recurrencias y poner un ejemplo sencillo. No es necesario dar una justificación del método.

3. Describe un algoritmo que calcule el número de formas distintas de repartir n objetos iguales entre tres receptores A, B y C de modo que A reciba al menos cuatro y B y C reciban al menos dos, pero que C no reciba más de cinco.

Para resolver el problema con un número n (adecuado) se ha de calcular el coeficiente de x^{n} en la siguiente serie:

(x^{4} + x^{5} + ⋯) (x^{2} + x^{3} + ⋯) (x^{2} + x^{3} + x^{4} + x^{5})

4. Calcular la probabilidad de que una permutación σ de {1, 2, …, n} satisfaga la propiedad:

∃ i ∈ {1, 2, …, n} tal que σ(i) = i

justificando la respuesta.

Se puede utilizar el hecho de que D(n) = n! ∑_{k=0}^{n} \frac{(−1)^{k}}{k!} donde D(n) es el número de desarreglos de n objetos y por lo tanto, el número de permutaciones de n objetos que satisface la propiedad propuesta es n! − D(n) y pa probabilidad solicitada es:

\frac{n! − D(n)}{n!} = 1 − \frac{D(n)}{n!}

que es una cantidad que tiende a \frac{e−1}{e} cuando n crece.

 $ maple
    |\^/|     Maple V Release 2 (Universidade Da Coruna)
._|\|   |/|_. Copyright (c) 1981-1993 by the University of Waterloo.
 \  MAPLE  /  All rights reserved. Maple and Maple V are registered
 <________>  trademarks of Waterloo Maple Software.
      |       Type ? for help.

> p:= n -> 1-(sum('(-1)**k/k!','k'=0..n));

    /   n           \
    | -----       k |
    |  \      (-1)  |
p := n -> 1 - |   )    '-----'|
    |  /        k!  |
    | -----         |
    \'k' = 0        /
--------------------------------------------------------------------------------
> for r from 0 to 20 do evalf(p(r)) od;
     0
    1.
.5000000000
.6666666667
.6250000000
.6333333333
.6319444444
.6321428571
.6321180556
.6321208113
.6321205357
.6321205608
.6321205587
.6321205588
.6321205588
.6321205588
.6321205588
.6321205588
.6321205588
.6321205588
.6321205588
--------------------------------------------------------------------------------
>  evalf((1-1/E));
.6321205588
--------------------------------------------------------------------------------
>