SUCESIONES Y FUNCIONES DEFINIDAS POR RECURREN-

CIA
1.Deniciones
Una sucesion {u
n
} tal que
u
n+1
3u
n
= n
o u
n+2
+ 4u
n+1
2u
n
= 0,
o, mas generalmente
u
n+k
+ a
1
u
n+k1
+ + a
k
u
n
= f(n),
donde los coecientes a
i
pueden ser funciones de n o constantes (es decir,
independientes de n), recibe el nombre de ecuacion en diferencias nitas o ecuacion
recurrente. Si f(n) = 0, la ecuacion se dira homogenea.
2.Ecuaciones lineales homogeneas de primer orden con coecientes
constantes
Sea k = 0 una constante dada, y {u
n
} una sucesion que satisface
u
n+1
ku
n
= 0, n 1 (1).
Entonces :
i) u
n
= A k
n
, donde A es una constante, es una solucion de (1).
ii) Toda sucesion que verique (1) debe ser de esa forma.
Demostracion
i) Si u
n
= A k
n
, entonces u
n+1
ku
n
= A
_
k
n+1
k
n+1
_
= 0.
ii)Si u
n
verica la ecuacion, entonces
u
n
= ku
n1
= k
2
u
n2
= = k
n1
u
1
,
as

i que llamando A = u
1
/k resulta en efecto u
n
= A k
n
.
Se dice que A k
n
es la solucion general de la ecuacion (1).
3.Ecuaciones lineales homogeneas de segundo orden con coecientes
constantes
Sean p, q dos constantes dadas, con q = 0. Supongamos que se verica
u
n+2
pu
n+1
+ qu
n
= 0, n 1 (2),
y sean , las ra

ices de la ecuacion
x
2
px + q = 0,
que se llama ecuacion caracter

istica de (2). Entonces:

i) Si = , la solucion general de la (2) es de la forma
u
n
= A
n
+ B
n
,
1
www.cienciamatematica.com
donde A y B son constantes que se determinaran por los valores iniciales de
la sucesion u
n
, es decir, u
1
y u
2
.
ii) Si = , entonces la solucion general de (2) es
u
n
= (A + Bn)
n
.
Demostracion de i)
Por las propiedades de las ra

ices de la ecuacion de segundo grado (o formulas

de Cardano-Vieta), es claro que + = p, = q.
Entonces la ecuacion (2) se escribe como
u
n+2
( + ) u
n+1
+ u
n
= 0.
Si u
n
= A
n
+ B
n
, se tiene
u
n+2
( + ) u
n+1
+u
n
= A
n
_

2
( + ) +

+B
n
_

2
( + ) +

=
0
porque los dos corchetes valen 0.
Para probar el rec

iproco, escribamos (2) en la forma

(u
n+2
u
n+1
) (u
n+1
u
n
) = 0 v
n+1
v
n
= 0.
Por lo visto en las ecuaciones de primer orden, debera ser
u
n+1
u
n
= A
n
(3) para alguna constante A.
Si volvemos a escribir (2) en la forma
(u
n+2
u
n+1
) (u
n+1
u
n
) = 0, debera ser ahora
u
n+1
u
n
= B
n
(4) para alguna constante B.
De (3) y (4) podemos despejar facilmente u
n
:
u
n
=
B

n
+
A

n
,
que es de la forma anunciada. Esto demuestra i).
El argumento anterior falla justamente cuando = , porque entonces (3)
y (4) son identicas.
Con objeto de probar el rec

iproco en este caso, pongamos u

n
= v
n

n
.
Entonces v
n
satisface la ecuacion v
n+2
2v
n+1
+ v
n
= 0.
Admitiremos sin demostracion que v
n
= An+B, es decir, que la sucesion v
n
es una progresion aritmetica. Sabemos que las progresiones aritmeticas verican
la ecuacion anterior, es decir, cada termino es media aritmetica del anterior y
el siguiente. Lo que necesitamos es que, rec

iprocamente, cualquier sucesion que

verique dicha ecuacion es una progresion aritmetica. Eso es justamente lo que
no demostramos.
4.Generalizacion
a)La solucion general de la ecuacion
2
www.cienciamatematica.com
u
n
+ pu
n1
+ qu
n2
+ ru
n3
= 0
es
u
n
= A
n
+ B
n
+ C
n
,
donde , , son las ra

ices de la ecuacion caracter

istica
x
3
+ px
2
+ qx + r = 0,
cuando las ra

ices son distintas.

Si = = , la solucion es u
n
= (A + Bn)
n
+ C
n
.
Si = = , la solucion es u
n
=
_
A + Bn + Cn
2
_

n
.
5.Ejemplos
Si u
n
y v
n
son dos sucesiones recurrentes denidas por
u
n
+ pu
n1
+ qu
n2
= 0, v
n
+ p

v
n1
+ q

v
n2
= 0,
y se verica que p
2
= 4q, p
2
= 4q

, entonces llamando
(, ) a las ra

ices de x
2
+ px + q = 0,
(

) a las ra

ices de x
2
+ p

x + q

= 0,
se tiene
z
n
= u
n
v
n
= A
n

n
+ B
n

n
+ C
n

n
+ D
n

n
que verica una ecuacion de la forma
z
n
pp

z
n1
+
_
p
2
q

+ p

q
2
2qq

_
z
n2
pp

qq

z
n3
+ q
2
q
2
z
n4
= 0
b) Si u
n
= Cn 2, obtener la ecuacion recurrente vericada por u
n
.
Se trata de eliminar C entre las expresiones para u
n
y u
n1
= C (n 1)2;
resulta
(n 1) u
n
nu
n1
= 2.
c)Las sucesiones u
n
, v
n
verican las recurrencias
u
n
= u
n1
+ u
n2
; v
n
= v
n1
+ v
n2
+ v
n3
.
Determinar la recurrencia vericada por s
n
= u
n
+ v
n
.
Las ecuaciones caracter

isticas de ambas recurrencias son

x
2
x 1 = 0, con ra

ices x
1
, x
2
y
3
y
2
y 1 = 0, con ra

ices y
1
, y
2
, y
3
.
3
www.cienciamatematica.com
Por lo tanto
u
n
= a
1
x
n
1
+ a
2
x
n
2
, v
n
= b
1
y
n
1
+ b
2
y
n
2
+ b
3
y
n
3
.
Por lo tanto el termino general de s
n
vendra dado por
s
n
= a
1
x
n
1
+ a
2
x
n
2
+ b
1
y
n
1
+ b
2
y
n
2
+ b
3
y
n
3
.
La ecuacion caracter

istica de esta recurrencia debe tener las ra

ices x
1
, x
2
, y
1
, y
2
, y
3
.La
forma mas sencilla de obtener un polinomio con estas ra

ices es poniendo
_
t
2
t 1
_ _
t
3
t
2
t 1
_
= t
5
2t
4
t
3
+ t
2
+ 2t + 1
y por lo tanto la recurrencia buscada sera
s
n
= 2s
n1
+ s
n2
s
n3
2s
n4
s
n5
.
5.Ecuaciones no homogeneas
Si f(n) no es identicamente nula, la ecuacion se dice no homogenea.
Sea tal ecuacion
au
n
+ bu
n1
+ + pu
nr
= k, (5)
donde a, b, , p, k son funciones dadas de n o constantes, y r es jo.
En este caso,
1) La solucion general hace intervenir r constantes arbitrarias, que se deter-
minaran por los r primeros terminos de la sucesion.
2) Si v
n
es la solucion general de la ecuacion homogenea
au
n
+ bu
n1
+ + pu
nr
= 0,
y w
n
es una solucion particular de la ecuacion no homogenea, entonces la
solucion general de (5) es v
n
+ w
n
.
Veamos mediante un ejemplo como se debe proceder.
Resolver la ecuacion
u
n
5u
n1
+ 6u
n2
= n
2
+ 5
n
+ 2
n
.
La solucion general de la ecuacion homogenea u
n
5u
n1
+ 6u
n2
= 0 es
u
n
= A 2
n
+ B 3
n
,
porque la ecuacion caracter

istica x
2
5x + 6 = 0 tiene como ra

ices a 2 y 3.
Busquemos primero una solucion particular de la ecuacion u
n
5u
n1
+
6u
n2
= n
2
. Intentamos como solucion de prueba una funcion que sea un poli-
nomio de segundo grado en n :
u
n
= a + bn + cn
2
sustituyendo en la ecuacion e igualando los coecientes de las potencias de n
con el mismo exponente en ambos miembros obtenemos el sistema de ecuaciones
4
www.cienciamatematica.com
2c = 1, 2b 14c = 0, 2a 7b + 19c = 0
que tiene como solucion unica c =
1
2
, b =
7
2
, a =
15
2
, as

i que la solucion
particular es de la forma
u
n
=
1
2
_
n
2
+ 7n + 15
_
.
Ahora probaremos con la ecuacion u
n
5u
n1
+ 6u
n2
= 5
n
, con la que
intentamos una solucion de prueba de la forma u
n
= a.5
n
; entonces
a
_
5
n
5.5
n1
+ 6.5
n2
_
= 5
n
=a =
25
6
=u
n
=
1
6
5
n+2
Por ultimo consideramos la ecuacion u
n
5u
n1
+ 6u
n2
= 2
n
.
Como 2 es una ra

iz de la ecuacion caracter

istica, esta claro que a 2

n
no
puede ser una solucion. Intentamos entonces u
n
= an 2
n
, con lo que
a
_
n 2
n
5 (n 1) 2
n1
+ 6 (n 2) 2
n2

= 2
n
=a = 2 =u
n
= n2
n+1
Entonces, la solucion general de la ecuacion u
n
5u
n1
+6u
n2
= n
2
+5
n
+2
n
es
u
n
=
1
2
_
n
2
+ 7n + 15
_
+
1
6
5
n+2
+ (A2n) 2
n
+ B 3
n
6.Algunas funciones de Teor

ia de N umeros denidas recurrente-

mente
Ejemplo 1: Sea g : N N dada por
g (0) = 1 ; g(n) = n g(n 1) si n = 0
Se conjetura sin mucha dicultad que
g(n) = n!,
probando la conjetura por induccion.
Ejemplo 2 : Sea h : N N N denida por :
si x < y, h(x, y) = x
si x y, h(x, y) = h(x y, y)
Formemos una tabla con valores peque nos de x e y, a la b usqueda de una
pista :
5
www.cienciamatematica.com
x\y 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0
1 0 1 1 1 1 1 1
2 0 0 2 2 2 2 2
3 0 1 0 3 3 3 3
4 0 0 1 0 4 4 4
5 0 1 2 1 0 5 5
6 0 0 0 2 1 0 6
7 0 1 1 3 2 1 0
Ademas, se tiene
h(7, 2) = h(5, 2) = h(3, 2) = h(1, 2) = 1
h(9, 2) = h(7, 2) = 1
h(12, 5) = h(7, 5) = h(2, 5) = 2
h(12, 3) = h(9, 3) = h(6, 3) = h(3, 3) = h(0, 3) = 0
En este ultimo ejemplo hemos aplicado la denicion de h cuatro veces (antes
de escribir el ultimo signo =), que expresa el n umero de veces que 12 esta
contenido en 3, y es el n umero de veces que aplicamos la segunda condicion
de la denicion de h antes de poder aplicar la primera. Esto nos indica que h
calcula el resto de la division de x por y.
Ejemplo 3 : Sea h la funcion del ejemplo anterior, y denamos k : N N N
mediante
k (x, 0) = x
k(x, y) = k(y, h(x, y)) si y = 0
Formemos la tabla de valores de la nueva funcion
x\y 0 1 2 3 4 5 6 7
0 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
2 2 1 2 1 2 1 2 1
3 3 1 1 3 1 1 3 1
4 4 1 2 1 4 1 2 1
5 5 1 1 1 1 5 1 1
6 6 1 2 3 2 1 6 1
7 7 1 1 1 1 1 1 7
Esta funcion da el maximo com un divisor de x e y.
Ejemplo 5: Denimos s : N N N mediante
s(x, 0) = x
s(x, y) = s(x, y 1) + 1
6
www.cienciamatematica.com
Observamos que
s(0, 1) = s(0, 0) + 1 = 0 + 1 = 1
s(0, 2) = s(0, 1) + 1 = 1 + 1 = 2
s(1, 1) = s(1, 0) + 1 = 1 + 1 = 2
s(1, 2) = s(1, 1) + 1 = 2 + 1 = 3
formando la tabla observamos enseguida que
s(x, y) = x + y
Ejemplo 6: Sea p : N N N denida por
p(x, 1) = x
p(x, y) = p(x, y 1) + x, si y = 1
Formando la tabla se identica la funcion como el producto de x por y:
p(x, y) = x y
En todos los ejemplos anteriores la conjetura se prueba por induccion, como
veremos detalladamente en el siguiente
Ejemplo 7: Sea w : N N N denida por
w(x, 1) = x
w(x, y) = x w(x, y 1), si y = 1
Comprobamos primero algunos valores :
w(1, 2) = 1 w(1, 1) = 1 1 = 1
w(2, 2) = 2 w(2, 1) = 2 2 = 4
w(2, 3) = 2 w(2, 2) = 2 4 = 2
3
= 8
w(3, 2) = 3 w(3, 1) = 3 3 = 9
w(3, 3) = 3 w(3, 2) = 3
3
= 27
La conjetura parece clara: w(x, y) = x
y
. Lo probaremos por induccion, en
dos partes (doble induccion)
a) Supongamos y jo; supongamos que w(x, y) = x
y
es cierto para todos los
valores naturales menores o iguales que x. Entonces
w(x + 1, y) = (x + 1) w(x + 1, y 1) =
= (x + 1) (x + 1) w(x + 1, y 2) =
= (y veces) = (x + 1)
y
.
7
www.cienciamatematica.com
b) Supongamos ahora que x es jo y que w(x, y) = x
y
es cierto para todo
n umero natural menor o igual que y; entonces
w(x, y + 1) = x w(x, y) = x x
y
= x
y+1
.
Ejemplo 8 : Sea d : N N

N denida por
d(x, y) = 0 si x < y
d(x, y) = d(x y, y) + 1 si x y
Al calcular los valores para la tabla obtenemos
d(2, 2) = d(0, 2) + 1 = 1
d(4, 2) = d(2, 2) + 1 = 2
d(6, 2) = d(4, 2) + 1 = d(2, 2) + 1 + 1 = 3
en este caso se obtiene el cociente entero por defecto de la division de x por
y.
Ejemplo 9 : Sea r : N N N denida por
r (x, x) = 0
r(x, y) = r(x 1, y) + 1 si x = y
Esta funcion da la diferencia entre x e y.
Ejemplo 10 : Sea m : N N denida por
m(0) = 1
m(x) = m(x 1) + 2x + 1
Esta funcion da los cuadrados de los n umeros naturales
Ejemplo 11 : Sea n : R Z denida por
n(x) = 0 si 0 x < 1
n(x) = n(x 1) + 1 si x 1
n(x) = n(x + 1) 1 si x < 0
Esta funcion es la parte entera de x.
Todos estos ejemplos est an tomados de la publicacion francesa 1984:Quince
a nos de los IREM y fueron preparados por la seccion de Bastia (Corcega) del
IREM de Niza para un experimento sobre Informatica con alumnos de Bachiller-
ato.
7.El metodo de las series formales para resolver recurrencias
8
www.cienciamatematica.com
Sabemos que un polinomio es una expresion de la forma
p(x) = a
0
+ a
1
x + a
2
x
2
+ + a
n
x
n
.
Una serie formal es, en cierto modo, algo mas simple:
a
0
+ a
1
x + a
2
x
2
+
La sumas y productos de series formales se denen de manera analoga a las
sumas y productos de polinomios. Por ejemplo
_
1 3x + 3
2
x
2
3
3
x
3
+
_
(1 + 3x) = 1 3x + 3
2
x
2
3
3
x
3
+
+3x 3
2
x
2
+ 3
3
x
3

= 1.
de modo que podemos escribir
1 3x + 3
2
x
2
3
3
x
3
+ =
1
1 + 3x
.
De manera algo mas general, podemos poner
1 + ax + a
2
x
2
+ =
1
1 ax
.
Veamos como se pueden aplicar estas series para encontrar soluciones de
ecuaciones recurrentes. Sea, por ejemplo, la sucesion
a
0
= 0, a
1
= 1, a
n+2
= 5a
n+1
6a
n
.
La idea es considerar la serie formal
f(x) = a
0
+ a
1
x + a
2
x
2
+
e intentar compactarla y despues descompactarla. Para eso, observemos
que
f(x) = a
0
+ a
1
x + a
2
x
2
+ a
3
x
3
+
5xf(x) = 5a
0
x 5a
1
x
2
5a
2
x
3

6x
2
f(x) = 6a
0
x
2
+ 6a
1
x
3
+
Sumando las ecuaciones, se observa que, por la ecuacion recurrente original,
los coecientes de los terminos de grado mayor o igual que 2 se anulan, y nos
quedamos con
_
1 5x + 6x
2
_
f(x) = a
0
+ (a
1
5a
0
) x f(x) =
x
1 5x + 6x
2
9
www.cienciamatematica.com
Ya tenemos f(x) compactada (esta funcion se llama funcion generatriz de
la recurrencia). Como descompactarla? El metodo (truco que se aplica dos
veces) consistira en descomponerla en trozos que sepamos como descompactar :
1 5x + 6x
2
= (1 2x) (1 3x)
Busquemos n umeros a, b tales que
a
1 2x
+
b
1 3x
=
x
1 5x + 6x
2
Haciendo operaciones, llegamos a la identicacion entre los polinomios sigu-
ientes:
(a + b) (3a + 2b) x = x
que, por identicacion de coecientes, conduce al sistema
a + b = 0, 3a+2b=-1
cuya solucion unica es a = 1, b = 1.
Entonces
f(x) =
x
1 5x + 6x
2
=
1
1 3x

1
1 2x
=
=
_
1 + 3x + 3
2
x
2
+
_

_
1 + 2x + 2
2
x
2
+
_
=
=
_
3
0
2
0
_
+
_
3
1
2
1
_
x +
_
3
2
2
2
_
x
2
+
as

i que el coeciente de x
n
, que es lo que buscamos, sera
a
n
= 3
n
2
n
Como ejercicio, buscar, mediante series formales, la expresion cerrada para
el termino general F
n
de la sucesion de Fibonacci :
F
0
= 0, F
1
= 1, F
n+2
= F
n+1
+ F
n
.
Algunos problemas de concursos donde aparecen funciones o suce-
siones denidas recurrentemente.
Los problemas de recurrencias que se han ido proponiendo en Concursos y
Olimpiadas son, como es natural, bastante complicados. Casi nunca basta en
ellos conocer solamente los metodos de resolucion de ecuaciones recurrentes que
hemos expuesto al principio. Veamos algunos ejemplos.
Problema 1
Sean a y b enteros positivos jos. Hallar la solucion general de la ecuacion
recurrente
x
n+1
= x
n
+ a +
_
b
2
+ 4ax
n
, n 0, x
0
= 0 (1)
10
www.cienciamatematica.com
(Generalizacion de un problema propuesto por Alemania Federal, IMO 1981)
Solucion
El primer tecnicismo que hay que aplicar aqu

i consiste en expresar x
n
en
funcion de x
n+1
:
b
2
+ 4ax
n+1
= b
2
+ 4a
_
x
n
+ a +
_
b
2
+ 4ax
n
_
=
= 4a
2
+ 4a
_
b
2
+ 4ax
n
+
_
b
2
+ 4ax
n
_
=
=
_
2a +
_
b
2
+ 4ax
n
_
2
Por lo tanto
_
b
2
+ 4ax
n+1
= 2a +

b
2
+ 4ax
n
. (2)
Entonces, de (1) y (2) resulta
x
n
= x
n+1
+ a
_
b
2
+ 4ax
n+1
.
Sustituyendo aqu

i n por n 1 (Segundo tecnicismo), resulta

x
n1
= x
n
+ a
_
b
2
+ 4ax
n
(3)
luego de (1) y (3) resulta
x
n+1
+ x
n1
= 2a + 2x
n
x
n+1
2x
n
+ x
n1
= 2a
lo que por un lado indica que todos los terminos de la sucesion son enteros
; ademas resolver esta ecuacion recurrente no es dif

icil; pongamos
y
n1
= x
n
x
n1
con lo que y
n
y
n1
= 2a, y eso nos dice que y
n
es una progresion aritmetica
:
y
0
= x
1
x
0
= a + b
y
n
= 2an + (a + b)
de donde resulta
x
n
= an
2
+ bn
Problema 2
Si a
0
= 0, y k es un entero positivo, se dene
a
n+1
= (a
n
+ 1) k + (k + 1) a
n
+ 2
_
k (k + 1) a
n
(a
n
+ 1).
Demostrar que a
n
es entero positivo para todo n.
(Propuesto, pero no elegido, por Canada en la IMO 1983)
Solucion
11
www.cienciamatematica.com
Aqu

i, estrictamente hablando, no es necesario resolver la recurrencia prop-

uesta. Bastara escribirla eliminando los radicales.
Para eso la escribimos como
a
n+1
[(2k + 1) a
n
+ k] = 2
_
k (k + 1) a
n
(a
n
+ 1)
y elevamos al cuadrado ; resulta as

i
a
2
n+1
+ [(2k + 1) a
n
+ k]
2
2a
n+1
[(2k + 1) a
n
+ k]
= 4k (k + 1) a
2
n
+ 4k (k + 1) a
n
Reordenando terminos y simplicando, resulta
a
2
n
2 [k + (2k + 1) a
n+1
] a
n
+ (a
n+1
k)
2
= 0
De aqu

i obtenemos (tratandola como una ecuacion cuadratica en a

2
n
y te-
niendo en cuenta que la sucesion tiene que ser creciente)
a
n
= k + (2k + 1) a
n+1

_
[k + (2k + 1) a
n+1
]
2
(a
n+1
k)
2
= k + (2k + 1) a
n+1

_
((2k + 1) a
n+1
+ k + a
n+1
k) ((2k + 1) a
n+1
+ k a
n+1
+ k)
= k + (2k + 1) a
n+1

_
4k (k + 1) a
n+1
(a
n+1
+ 1)
Cambiando en la ecuaci on original n por n + 1 obtenemos
a
n+2
(2k + 1) a
n+1
k = 2
_
k (k + 1) a
n+1
(a
n+1
+ 1)
y teniendo en cuenta que lo que acabamos de obtener se puede escribir como
2
_
k (k + 1) a
n+1
(a
n+1
+ 1) = (2k + 1) a
n+1
+ k a
n
resulta la recurrencia
a
n+2
= 2 (2k + 1) a
n+1
a
n
+ 2k
que da valores enteros positivos, por ser creciente y a
0
= 0, a
1
= k.
Problema 3
Si m, n, r son enteros positivos, y 1 + m + n

3 =
_
2 +

3
_
2r1
, demostrar
que entonces m es un cuadrado perfecto.
(II Olimp.Iberoamericana, Uruguay 1987 ; solucion de Felipe Fritz Braga,
Mencion especial del Jurado por esta solucion)
Solucion
Considerando los conjugados, podemos escribir
1 + mn

3 =
_
2

3
_
2r1
,
as

i que, sumando miembro a miembro, resulta

12
www.cienciamatematica.com
1 + m =
_
2 +

3
_
2r1
+
_
2

3
_
2r1
2
y el segundo miembro recuerda la solucion de una ecuacion en diferencias;
los coecientes de la ecuacion caracter

istica deben ser -4 y 1, opuesto de la

suma y producto, respectivamente, de 2 +

3 y 2

3; as

i que eso conduce a

la ecuacion recurrente
f(r + 2) = 4f(r + 1) f(r)
cuya solucion es
f(r) =
_
2 +

3
_
r
1 +

3
+
_
2

3
_
3
1

3
De la recurrencia resulta que , al ser f(0) y f(1) enteros, lo es f(r) si r lo es;
entonces resulta
(f(r))
2
=
_
2 +

3
_
2r
4 + 2

3
+
_
2

3
_
2r
4 2

3
1
=
_
2 +

3
_
2r1
+
_
2

3
_
2r1
2
1 = m,
y hemos terminado.
Problema 4
Dado m N

,se dene la sucesion a

n
as

i:
a
1
= 2 (m + 1)
a
n+1
=
1
4m
_
ma
n
1 +

1 + 2ma
n
_
Obtener una expresion expl

icita para a
n
en funcion de n y m
(Gazeta Matematica 1988, Rumania)
Solucion
La sucesion es creciente.
Para intentar expresar a
n
en funcion de a
n+1
, ponemos
4ma
n+1
ma
n
+ 1 =

1 + 2ma
n
;
elevando al cuadrado y reordenando seg un las potencias de a
n
se obtiene,
despues de simplicar por m :
ma
2
n
2 [2m(2ma
n+1
+ 1)] a
n
+ 8a
n+1
(2ma
n+1
+ 1) = 0;
despejando a
n
(y eligiendo el signo menos delante del radical por ser creciente
la sucesion)
13
www.cienciamatematica.com
a
n
=
2 (2ma
n+1
+ 1) 2

2ma
n+1
+ 1
m
que escribimos
2 (2ma
n+1
+ 1) ma
n
= 2
_
2ma
n+1
+ 1.
Cambiando n por n+1 en la primera expresion y multiplicando por 2 resulta
8ma
n+2
2ma
n+1
+ 2 = 2
_
2ma
n+1
+ 1
As

i que llegamos a la recurrencia

8a
n+2
6a
n+1
+ a
n
= 0,
cuya ecuacion caracter

istica es x
2

3
4
x +
1
8
= 0, de ra

ices
1
2
y
1
4
.
Por tanto, la solucion de la recurrencia es
a
n
= A
_
1
2
_
n
+ B
_
1
4
_
n
.
Los valores iniciales son a
1
= 2 (m + 1), a
2
= (m + 2)/2, luego el sistema
para determinar las constantes A y B es
8 (m + 1) = 2A + B, 8(m + 2) = 4A + B
con solucion
A = 4, B = 8m
as

i que la expresion expl

icita para a
n
sera
a
n
= 4
_
1
2
_
n
+ 8m
_
1
4
_
n
.
Problema 5 (sin solucion)
Sea k un entero positivo. Se considera la sucesion
x
1
= k, x
n+1
= kx
n
+
_
(k
2
1) (x
2
n
1).
Demostrar que todos los x
n
son enteros positivos
(Competicion K urschak, Hungr

ia, 1988)
Problema 6 (sin solucion)
La sucesion (x
n
) se dene mediante
x
1
= 0, x
n+1
= mx
n
+
_
(m
2
1) x
2
n
+ p
2
, con m N

, p Z .
Demostrar que todos los terminos de la sucesion son enteros.
(Mihaela Pal, Gazeta Matematica, Rumania 1990)
Problema 7
14
www.cienciamatematica.com
Determinar la funcion f : N N , siendo N = {1, 2, 3, } el conjunto
de los n umeros naturales, que cumple, para cualesquiera s, n N , las dos
condiciones siguientes:
a) f(1) = f(2
s
) = 1, y
b) si n < 2
s
, entonces f(2
s
+ n) = f(n) + 1.
Calcular el valor maximo de f(n) cuando n 2001.
Hallar el menor n umero natural n tal que f (n) = 2001.
(Problema 6, O.M.E. 2001, Fase Final)
Solucion.
Puesto que a) da los valores de f en las potencias de 2, no parece descabellado
escribir al lado de n su expresion en el sistema binario de numeracion.
Para intentar entender como act ua f, formaremos una tabla de valores rel-
ativamente amplia:
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
n
(2
1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111
f(n) 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4
n 16 17 18
n
(2
10000 10001 10010
f(n) 1 2 2
etc.
A la vista de la tabla, conjeturamos que f(n) da la suma (en base 10) de las
cifras de n escrito en base 2, y trataremos de probarlo por induccion.
Si n = 1 o es una potencia de 2, f(n) = 1.
Si n > 1 y no es una potencia de 2, supongamos conocido f(m) para todo
m < n; entonces se puede escribir n = 2
x
+ m, tomando como 2
x
la mayor
potencia de 2 que es menor que n, y entonces
f(n) = f(2
x
+ m) = f(m) + 1.
Una vez probada la conjetura por induccion, contestemos a las dos preguntas
que plantea el problema:
En el primer caso, se trata de ver cuantos unos puede tener como maximo
un n umero menor o igual que 2001 escrito en base 2 : ese n umero, escrito en
base 2, es 1111111111
(2
= 1023=2
10
1, luego f(n) = 10.
En el segundo caso, un razonamiento similar demuestra que n = 2
2001
1.
Problema 8
Sea f la funcion denida sobre los enteros positivos mediante
f(1) = 1, f(3) = 3
f(2n) = f(n)
f(4n + 1) = 2f(2n + 1) f(n)
f(4n + 3) = 3f(2n + 1) 2f(n)
15
www.cienciamatematica.com
para todo n natural.
Determinar el n umero de enteros positivos n, menores o iguales que 1988,
tales que f(n) = n.
(Problema #3,IMO 1988, propuesto por Gran Breta na)
Solucion
A la b usqueda de una pista, encontramos
n : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
f(n) : 1 1 3 1 5 3 7 1 9 5 13 3 11 7 15 1 17
Puede observarse que
f(2
k
) = 1, f(2
k
1) = 2
k
1, f(2
k
+ 1) = 2
k
+ 1,
as

i que parece que puede resultar util el sistema de numeracion binario.

Convirtamos la tabla mediante el sistema de base 2:
n n
(2
f(n) [f(n)]
(2
1 1 1 1
2 10 1 1
3 11 3 11
4 100 1 1
5 101 5 101
6 110 3 11
7 111 7 111
8 1000 1 1
9 1001 9 1001
10 1010 5 101
11 1011 13 1101
12 1100 3 11
13 1101 11 1011
14 1110 7 111
15 1111 15 1111
16 10000 1 1
17 10001 17 10001
A la vista de la tabla, conjeturamos que
f(n) se obtiene invirtiendo la expresion binaria de n (ignorando los ceros
iniciales que puedan obtenerse).
Si se consigue probar esta conjetura, los n tales que f(n) = n seran los
n umeros que en escritura binaria son capic uas, y son los que habra que contar
despues.
Probaremos la conjetura por induccion. Ciertamente se cumple para n < 8.
Supongamos que se cumple para todo n < 4m, entonces sera suciente probar
que se cumple para n = 4m, 4m + 1, 4m + 2, 4m + 3.
Escribimos m en el sistema binario : m = (
k

k1

1

0
)
2
, donde las cifras

i
son 0 o 1. Entonces
16
www.cienciamatematica.com
2m = (
k

k1

1

0
0)
2
2m + 1 = (
k

k1

1

0
1)
2
4m = (
k

k1

1

0
00)
2
4m + 1 = (
k

k1

1

0
01)
2
4m + 2 = (
k

k1

1

0
10)
2
4m + 3 = (
k

k1

1

0
11)
2
Por lo tanto,
f(4m) = f(2m) = (
0

1

k1

k
)
2
= expresion invertida de 4m
(recuerdese que 2m < 4m y por lo tanto se aplica la hipotesis de induccion
: se invierten las cifras de 2m).
Por otra parte,
f(4m + 1) = 2f(2m + 1) f(m) =
= 2 (1
0

1

k1

k
)
2
(
0

1

k1

k
)
2
=
= 2
k+2
+ 2 (
0

1

k1

k
)
2
(
0

1

k1

k
)
2
=
= 2
k+2
+ (
0

1

k1

k
)
2
= (10
0

1

k1

k
)
2
=
= expresion invertida de 4m+1
Analogamente,
f(4m + 2) = f(2m + 1) = (1
0

1

k1

k
) =
= expresion invertida de 4m+2
y, nalmente,
f(4m + 1) = 3f(2m + 1) 2f(m) =
= 3 (1
0

1

k1

k
)
2
2 (
0

1

k1

k
)
2
=
= 3 2
k+1
+ (
0

1

k1

k
)
2
= (11
0

1

k1

k
)
2
=
= expresion invertida de 4m+3.
Por lo tanto, la conjetura ha quedado probada por induccion.
Vamos a contar los n < 1988 que son capic uas en binario.
Como 2
10
< 1988 < 2
11
= 2048, y 1988 = (11111000100)
2
, un n umero
capic ua con 2k cifras esta determinado por sus primeras k cifras. En nuestro
caso, el n umero de capic uas con 2,4,6,8,o 10 cifras binarias es 2
0
+2
1
+2
2
+2
3
+
2
4
= 31.
Un n umero capic ua con 2k + 1 cifras binarias depende de k 1 cifras, y
con k + 1 cifras hay 2
k
. En nuestro caso, con 1,3,5,7,9,11 cifras binarias hay
1 + 2 + 2
2
+ 2
3
+ 2
4
= 63.
17
www.cienciamatematica.com
Como los capic uas de 11 cifras
111111011111
2
y 11111111111
2
son mayores que 1988, el n umero buscado es 31+63-2=92.
Problema 9
Una variante del problema de Flavio Josefo
n personas estan dispuestas en c

irculo, numeradas del 1 a n. Contando en

el c

irculo, de 2 en dos, cada segunda persona es eliminada. El proceso se repite

hasta que queda una unica persona . Cual es el n umero que tiene el super-
viviente, J(n)?
Solucion
Comencemos con el caso particular en que n = 10. Empezamos a contar
en el 1, y el orden de eliminacion es 2,4,6,8,10,3,7,1,9. As

i pues, J(10) = 5.
Podr

iamos conjeturar que J(n) = n/2 cuando n es par, y el caso n = 2 apoyar

ia
esta conjetura; pero unos pocos casos peque nos nos disuaden (la conjetura falla
si n = 4 o si n = 6) :
n 1 2 3 4 5 6
J(n) 1 1 3 1 3 5
Parece que J(n) siempre es impar ; hay una buena razon para ello : en la
primera ronda quedan eliminados todos los n umeros pares. Ademas, si n es
par se llega a una situacion similar a la del principio, solo que queda la mitad
de personas, y sus n umeros han cambiado. Entonces, vamos a suponer que
18
www.cienciamatematica.com
inicialmente hay 2n personas.
Despues de la primera ronda quedan 1,3,5, , 2n 3, 2n 1 y el siguiente
en ser eliminado es el 3. Esto es lo mismo que empezar con n personas, excepto
que el n umero de cada persona ha sido duplicado y disminuido en uno, es decir
J(2n) = 2 J(n) 1, para n 1.
A partir de aqu

i, vamos obteniendo, por ejemplo,

J(20) = 2J(10) 1 = 9, J(40) = 17, y podr

iamos deducir que

J(5 2
m
) = 2
m+1
+ 1.
19
www.cienciamatematica.com
Pasemos al caso impar.
Aqu

i, la persona n umero 1 es eliminada despues de la persona 2n, y nos

quedan los n umeros de la parte interior del c

irculo en la gura anterior. De

nuevo casi tenemos la situacion original con n personas, pero ahora sus n umeros
son duplicados y aumentados en 1. Es decir.
J(2n + 1) = 2 J(n) + 1, n 1.
Con estos valores, junto con J(1) = 1, se tiene denido J en todos los casos:
J(1) = 1
J(2n) = 2 J(n) 1, para n 1.
J(2n + 1) = 2 J(n) + 1, n 1
Nuestra recurrencia hace posible construir una tabla para valores peque nos
de n muy rapidamente.
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
J(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1
Parece que podemos agrupar por potencias de 2; J(n) siempre vale 1 en
esas potencias, y aumenta de 2 en 2 dentro de cada grupo. Luego si escribimos
n = 2
m
+ k, donde 2
m
es la mayor potencia de 2 que es menor que n, y k es lo
que queda, parece que la solucion de nuestra recurrencia es
20
www.cienciamatematica.com
J(2
m
+ k) = 2k + 1, m 0, y 0 k < 2
m
(*)
(Observese que si 2
m
n < 2
m+1
, entonces la diferencia k = n2
m
verica
0 k < 2
m+1
2
m
= 2
m
).
Probaremos la conjetura por induccion, en este caso sobre m.
Cuando m = 0, debe ser k = 0; esto corresponde, en efecto, a J(1) = 1,
que es verdad. La induccion tiene dos partes, seg un que k sea par o impar. Si
m > 0, y 2
m
+ k = 2n, entonces k es par, y
J(2
m
+ k) = 2 J(2
m1
+
k
2
) 1 = 2
_
2k
2
+ 1
_
1 = 2k + 1,
que es lo que quer

iamos. Para ver que la conjetura tambien funciona en el caso

impar, cuando 2
m
+ k = 2n + 1, observese que la recurrencia implica que
J(2n + 1) J(2n) = 2,
o bien seguir un razonamiento analogo al anterior. En cualquier caso, hemos
obtenido el objetivo, si bien la relacion (*) no es exactamente una formula
cerrada, porque hace intervenir el n umero k, que es variable.
Puede resultar instructivo, siguiendo los pasos de la solucion del problema
anterior, ver lo que ocurre cuando n y J(n) se escriben en base 2 (dado el papel
relevante de las potencias de 2 en este problema, no tiene nada de raro usar el
sistema binario) :
Supongamos que
n = (b
m
b
m1
b
1
b
0
)
2
, con b
m
= 1,
ya que suponemos 2
m
< n < 2
m+1
.
Recordando que n = 2
m
+ k, se tiene, sucesivamente,
n = (1b
m1
b
1
b
0
)
2
k = (0b
m1
b
1
b
0
)
2
2k = (b
m1
b
1
b
0
0)
2
2k + 1 = (b
m1
b
1
b
0
1)
2
J(n) = (b
m1
b
1
b
0
b
m
)
2
donde la ultima etapa se sigue de J(n) = 2k + 1 y porque b
m
= 1.
Es decir, hemos probado que
J((b
m
b
m1
b
1
b
0
)
2
) = (b
m1
b
1
b
0
b
m
)
2
.
Problema 10(sin solucion)
Sea la funcion f, denida sobre el conjunto {1, 2, 3, } mediante
21
www.cienciamatematica.com
f(1) = 1
f(2n + 1) = f(2n) + 1
f(2n) = 3 f(n)
Determinar el conjunto de valores que toma f
(Problema #5, Olimp.Iberoamericana 1989; propuesto por Argentina)
Problema 11
Del polinomio P(x) se sabe que es de grado n y que,
si j = 1, 2, , n, n + 1, se verica P(j) = 2
j1
.
Calcular P(n + 2)
(Olimpiada de Israel,1988)
Solucion
Si P(x) tiene grado n, el polinomio P
1
(x) = P(x + 1) P(x) tiene grado
n 1; P
2
(x) = P
1
(x + 1) P
1
(x) tiene grado n 2, etc, as

i que nalmente se
llegara a un polinomio P
n
(x) de grado 0, es decir, constante. Usualmente esto
se dispone en forma de cuadro de las llamadas diferencias sucesivas del polinomio
P(x) :
P(x) 1 2 2
2
2
3
2
4
2
n1
2
n
P
1
(x) 1 2 2
2
2
3
2
n1
.
.
.
P
n2
(x) 1 2 2
2
P
n1
(x) 1 2
P
n
(x) 1
(en cada la aparecen las diferencias entre los valores consecutivos de la la
precedente).
Entonces se tiene (por la denicion de los polinomios P
i
) :
P(n + 2) = P(n + 1) + P
1
(n + 1) = P(n + 1) + P
1
(n) + P
2
(n) =
= P(n + 1) + P
1
(n) + P
2
(n 1) + P
3
(n 1) =
= P (n + 1) + P
1
(n) + P
2
(n 1) + P
3
(n 2) + + P
n1
(2) + P
n
(2) =
= 2
n
+ 2
n1
+ 2
n2
+ + 2
2
+ 2 + 1 = 2
n+1
1
Observacion : hay otra solucion, basada en la llamada formula de interpo-
lacion de Lagrange.
Problema 12
Sean x
n
e y
n
las sucesiones de n umeros naturales denidas por
x
0
= x
1
= 1, x
n+1
= x
n
+ 2x
n1
y
0
= 1, y
1
= 7, y
n+1
= 2y
n
+ 3y
n1
22
www.cienciamatematica.com
Demostrar que x
0
= y
0
= 1 es el unico termino com un a ambas sucesiones.
(USAMO 1973)
Observacion: La solucion ocial comienza diciendo : Calculemos los restos
de la division por 8 de x
n
e y
n
.... Aunque no se debe ser enemigo de las ideas
felices, estas no suelen aparecer por arte de magia, as

i que trataremos de dar

a la solucion un aspecto mas natural, si ello es posible...
Solucion
Los primeros valores de las sucesiones no proporcionan demasiada infor-
macion:
x
n
1 1 3 5 11
y
n
1 7 17 55 161
Resolvamos las dos ecuaciones en diferencias : las ecuaciones caracter

isticas
son, respectivamente,
(t 2) (t + 1) = 0,
(t 3)(t + 1) = 0
de las cuales resultan
x
n
=
1
3
_
2
n+1
+ (1)
n
_
y
n
= 2 3
n
(1)
n
.
Entonces, para que sea x
n
= y
m
, debe vericarse
3
m+1
2
n
=
1
2
[3 (1)
m
+ (1)
n
] .
Si n = 0 o n = 1, la unica solucion posible es m = 0.
Tomemos n 2. Si m y n son de la misma paridad, la ecuacion no puede
vericarse, porque el segundo miembro es par y el primero es impar. Si m
y n son de distinta paridad, observando los restos de la division por 4 de las
potencias de 3 y de 2, se obtiene
3
0
1 2
0
1
3
1
3 2
1
2
3
2
1 2
2
0
3
3
3 2
3
0
3
4
1 2
4
0
etc., as

i que el resto de la division por 4 del primer miembro de la ultima

igualdad sera 1 o 3.
Si m = 2k, n = 2h + 1, entonces 3
m+1
2
n
= 3
2k+1
2
2h+1
3 mientras
que el segundo miembro da resto 1 al ser dividido por 4.
23
www.cienciamatematica.com
Si m = 2k 1, n = 2h, entonces 3
m+1
2
n
= 3
2k
2
2h
1 mientras que el
segundo miembro es 1 3.
Por lo tanto la igualdad es imposible.
Problema 13
Construir una funcion f : N N N N tal que
f(f(n, m)) = (m, n)
(De un concurso rumano)
Solucion
Supongamos escritos los n umeros n y m mediante su descomposicion en
producto de potencias de factores primos :
n 2
1
3
2
5
3
7
4
(
1
,
2
,
3
,
4
, )
m 2
1
3
2
5
3
7
4
(
1
,
2
,
3
,
4
, )
Entonces se dene f de la siguiente manera :
f(n, m) =
_
2
2
3
1
5
4
7
3
, 2
2
3
1
5
4
7
3

_
que se comprueba verica la propiedad requerida :
f(f(n.m)) =
_
2
1
3
2
5
3
7
4
, 2
1
3
2
5
3
7
4

_
Problema 14
Sea p un n umero natural jo y x
0
> 0. Demostrar que entre los m primeros
terminos de la sucesion denida por
x
n+1
=
_
1 + p
2
x
n
+ p
_
1 + x
2
n
,
hay al menos
_
m
3

n umeros irracionales.
[] es la parte entera.
(Titu Andreescu, Gazeta Matematica 1980, Rumania)
Solucion de M
a
Ascension Lopez Chamorro
Haciendo operaciones en la ecuacion dada obtenemos
_
x
n+1
x
n
_
1 + p
2
_
2
= p
2
_
1 + x
2
n
_

x
2
n+1
+ x
2
n
2x
n+1
x
n
_
1 + p
2
= p
2
;
completando cuadrados en el primer miembro obtenemos
(x
n+1
+ x
n
)
2
2x
n+1
x
n
_
1 +
_
1 + p
2
_
= p
2
.
Esta ecuacion signica que, si x
n
y x
n+1
fueran racionales, tambien lo ser

ia
_
1 + p
2
, lo cual es absurdo. Por lo tanto, no hay dos terminos consecutivos
en la sucesion que sean racionales, o lo que es lo mismo, de cada 3 terminos
consecutivos, al menos uno (el de en medio) es irracional, as

i que, de los m
primeros, al menos
_
m
3

deben ser irracionales.

24
www.cienciamatematica.com