Download Coeficientes binomiales.

Coecientes binomiales.
Se recomienda que todos los problemas sean resueltos sin hacer uso del principio de inducción
matemática.
Teoremas y ejercicios fundamentales.
1. Un bicho se encuentra en el origen O = (0, 0) en el plano cartesiano. El bicho salta de un punto de
coordenadas enteras a otro, un salto por segundo, en el plano siguiendo el siguiente patrón: Del
punto (m, n) brinca al (m, n + 1) o al (m + 1, n), con la misma probabilidad de elegir cualquiera.
¾Donde puede encontrarse el bicho después de 5 segundos? ¾Es igual de probable que el bicho se
encuentre en cualquiera de esos puntos?
2. Empezando en el punto (0, 0), un objeto se mueve en el plano debido a una secuencia de pasos,
cada uno de longitud 1. Cada paso es a la izquierda, derecha, arriba o abajo, cada uno igual de
probable que el otro. ¾Cuál es la probabilidad de que el objeto alcance el punto (2, 2) en seis
pasos o menos?
3. Las licencias de conducir consisten de 8 dígitos. Se llaman par si contienen una cantidad par de
0's. Encuentra el número de licencias pares.
4.
1
Teorema del Binomio.
Sea n un entero positivo. Entonces
n n
n n−1
n n−2 2
n n
(a + b) =
a +
a
b+
a
b + ··· +
b .
0
1
2
n
n
5. Sean n y k enteros positivos con n ≥ k. Las siguientes propiedades de los coecientes binomiales
son ciertas:2
a)
b)
c)
n
k =
n+1
k+1
n
0 <
d)
k
e)
k
f)
g)
h)
i)
j)
k)
n
k
n
k
n
n−k ;
n
= nk + k+1
;
n
n
1 < 2 < ···
=n
n−1
k−1
n
n
= b n+1
;
< d n−1
e
c
2
2
;
n
= (n − k + 1) k−1
;
n
n+1
n+2
+ 2 + · · · + n+k
= n+k+1
;
0 +
1
k
k
n
n+1
+ n+2
+ · · · + n+k
= n+k+1
n +
n
n
n
n+1 ;
n
n
n
n
0 + 1 + ··· + n = 2 ;
n n
n
n
n
0 − 1 + 2 − · · · + (−1)
n = 0;
n
n
n
n
n−1
;
1 + 2 2 + 3 3 + · · · + n n = n2
n
k es divisible por n si n es primo y 1 ≤ k ≤ n − 1.
6. Evalúa
11
0
1
11
1
+
2
11
2
+
3
11
11
+ ··· +
12
.
1 También conocido como Teorema del Binomio de Newton.
2 Encuentre al menos una forma completamente combinatorias (usando estrategias de conteo) y al menos una forma
algebraica (de preferencia dos y esencialmente distintas) de probar estos enunciados.
1
7. Sea n ∈ N. Prueba que
n
k−1 X
(−1)
n
k
k=1
8.
a)
k
1
1
+ ··· + .
2
n
Pruebe que
11
1 X
40!
k=2
b)
=1+
k−1
29!
9
Pk−2
.
(40 − k)! =
1
31!
Encuentra y prueba la forma general del inciso anterior.
9. Sea {Fn }∞
n=0 una sucesión denida por F0 = F1 = 1 y Fn+2 = Fn+1 + Fn para n ≥ 0. Prueba
que
n X
k=0
n−k+1
k
= Fn+1 .
A la sucesión {Fn }∞
n=0 se le conoce como la sucesión
de Fibonacci
y Fn es el n-ésimo
número de
Fibonacci.
10. Sea n un entero positivo. Prueba que
n −1
X
n
i
i=0
11.
Vandermonde.
n+1
n + 1 X 2i
.
2n+1 i=1 i
=
Sean m, n y k enteros con m, n ≥ 0. Prueba que
X
k m+n
m
n
=
.
k
i
k−i
i=0
12. Sean n, k ∈ N con k+3 ≤ n. Prueba que
aritmética.
n
k
,
n
k+1
,
n
k+2
,
n
k+3
no pueden formar una progresión
13. En un torneo de todos contra todos,3 ocasionalmente ocurre un 3-set cíclico; esto es, un conjunto
{a, b, c} de tres equipos donde a le gana a b, b le gana a c, y c le gana a a. Si 23 equipos juegan
un torneo de todos contra todos (sin empates), ¾cuál es el mayor número de 3-set cíclicos que
pueden ocurrir?
14.
4
Sea p un primo, y sea n un entero positivo con n = (nm nm−1 . . . n0 )p .
Sea i un entero positivo menor que n. Además, escribimos a i = i0 + i1 p + · · · + im pm , donde
0 ≤ i0 , i1 , . . . , im ≤ p − 1. Entonces
Teorema de Lucas.
Y
m n
nj
≡
mód p.
i
ij
j=0
15.
a)
Sea n un entero positivo, y sea p un primo. Si pt | n!, entonces
t=
n
n
n
+ 2 + 3 + ··· .
p
p
p
3 A dichos torneos se les conoce también como torneos round-robin.
4 Sumamente importante.
2
b)
Sea p un primo, y sea n un entero positivo con n = (nm nm−1 . . . n0 )p . Si pt | n!, entonces
t=
n − (nm + nm−1 + · · · + n0 )
.
p−1
c ) Teorema de Kummer. Sea n e i enteros positivos con i
divide a ni si y sólo si t es menor o igual al número de
base p.
≤ n, y sea p un primo. Entonces pt
acarreos en la adición (n − i) + i en
16. Sea p un primo. Sea n un entero positivo, y sea n = (nm nm−1 . . . n0 )p la representación de n en
base p. Entonces:
a)
hay exactamente
b)
números entre
,
, . . . , nn , que no son divisibles por p;
n
p divide a cada uno de n1 , n2 , . . . , n−1
si y sólo si n = pk para algún entero positivo k; y
p no divide a ninguno de n0 , n1 , . . . , nn si y sólo si n = s · pk − 1 para algún entero positivo
n
0
c)
17.
n
1
(nm + 1) (nm−1 + 1) · · · (n0 + 1)
k y algún entero positivo s con 1 ≤ s ≤ p − 1.
a)
Prueba o refuta el siguiente enunciado: Para
cada entero positivo k, existe un entero positivo
n > 1 tal que el coeciente binomial ni es divisible por k para cualquier 1 ≤ i ≤ n − 1.
b ) Determina todos los enteros positivos k que satisfacen la siguiente propiedad: Existe un
entero positivo n > 1 (que depende de k) de manera que ni es divisible por k para cualquier
1 ≤ i ≤ n − 1.
Ejercicios
1. Sean n, m, k enteros no negativos tales que m ≤ n. Muestre que
n
k
n
n−m
=
.
k
m
m k−m
2. ¾Cuál es el valor del término constante en la expansión de x2 +
3. Sea n un entero positivo. Prueba que
n
X
k2
k=0
y que
n
= n (n + 1) 2n−2
k
n
k X
(−1) n
k=0
k+1
k
=
1
.
n+1
4. Sea n un entero no negativo. Prueba que
k
X
i=0
(−1)
i
n
k n−1
= (−1)
.
i
k
5. Sea n un entero impar. Prueba que el arreglo
n
n
n
,
, . . . , n−1
0
1
2
tiene una cantidad par de números impares.
3
1
x2
10
−2 ?
6. Sea n un entero positivo. Determina el número de números impares en
n
n
n
,
,...,
.
0
1
n
2n
k
7. Prueba que los coecientes binomiales
divisibles por 4.
, k = 1, 2, . . . , 2n−1 − 1, 2n−1 + 1, . . . , 2n − 1, son todos
8. Sea p un número primo. Prueba que
2p
≡2
p
mód p2 .
9. Sea n un entero no negativo. Muestra que
2
n
X
2n − 1
n
=n
.
k
n−1
k
k=0
10. an denota al número de conjuntos no vacíos S tales que
a)
S ⊆ {1, 2, . . . , n};
b)
todos los elementos de S tienen la misma paridad;
c ) cada elemento k ∈ S satisface que k ≥ 2 |S|, donde |S| denota al número de elementos de
S.
Prueba que
a2m−1 = 2 (Fm+1 − 1)
para toda m ≥ 1, donde Fn es el
n-ésimo
y
a2m = Fm+3 − 2
número de Fibonacci.
4