recorrencia e divisibilidade

Prévia do material em texto

Anotac¸o˜es Sobre Recorreˆncias e Somato´rios
Aplicados a Divisibilidade.
Rodrigo Carlos Silva de Lima ‡
rodrigo.uff.math@gmail.com
‡
1
Suma´rio
1 Recorreˆncias, somato´rios e divisibilidade 3
1.1 Recorreˆncia e divisibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Somato´rios e divisibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Recorreˆncias e nu´meros primos entre si . . . . . . . . . . . . . . . . . . . 9
1.4 Um resultado sobre nu´meros primos . . . . . . . . . . . . . . . . . . . . . 10
1.5 Interpolac¸a˜o e divisibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2
Capı´tulo 1
Recorreˆncias, somato´rios e
divisibilidade
1.1 Recorreˆncia e divisibilidade
Seja uma sequeˆncia (xn) que satisfaz uma recorreˆncia do tipo
x(n+p) = ap−1x(n+p−1) + ...+ a0xn
para todo n natural e p fixo natural . Sendo que os coeficientes ak sa˜o todos
inteiros. Nessas condic¸o˜es , se xk e´ divisı´vel por m para todo k de 0 ate´ p − 1 (as p
condic¸o˜es iniciais da recorreˆncia) enta˜o m|xn para todo n natural.
A demonstrac¸a˜o segue percebendo que a recorreˆncia dada implica que todos os
termos da sequeˆncia sa˜o combinac¸o˜es lineares ( com coeficientes inteiros ak) das
p condic¸o˜es iniciais que sa˜o todas divisı´veis por m, olhando a recorreˆncia em Zm
(congrueˆncia mod m) seria como se todas condic¸o˜es iniciais fossem nulas, logo
geramos uma sequeˆncia nula em Zm .
b Propriedade 1. Um polinoˆmio de grau p e´ divisı´vel por k para todo x natural
se e somente se f(0) ≡ · · · ≡ f(p) ≡ 0 mod k.
3
CAPI´TULO 1. RECORREˆNCIAS, SOMATO´RIOS E DIVISIBILIDADE 4
ê Demonstrac¸a˜o. Seja o polinoˆmio
f(x) =
p∑
k=0
akx
k
de grau p. Tem-se
∆p+1f(x) = 0 = (E− 1)p+1f(x) =
p+1∑
s=0
(
p+ 1
s
)
(−1)p+1−sf(x+ s) = 0
f(x+ p+ 1) = −
p∑
s=0
(
p+ 1
s
)
(−1)p+1−sf(x+ s)
f(p+ 1) = −
p∑
s=0
(
p+ 1
s
)
(−1)p+1−sf(s)
uma recorreˆncia de grau p + 1, temos que ter p + 1 condic¸o˜es iniciais para definir a
recorreˆncia, sendo dadas as f(0) ≡ · · · ≡ f(p) ≡ 0 modk sa˜o p+ 1 condic¸o˜es iniciais,
passando a recorreˆncia em Zk temos que todos os termos gerados pela recorreˆncia
sera˜o divisı´veis por k, pois todas condic¸o˜es iniciais sa˜o equivalentes a zero em Zk e
os termos da recorreˆncia dependem das condic¸o˜es iniciais apenas (e mais nenhum
termo constante, como mostra a recorreˆncia). Mostramos enta˜o a ida, se todas
condic¸o˜es iniciais sa˜o divisı´veis por k enta˜o enta˜o o polinoˆmio apresenta apenas
nu´meros divisı´veis por k quando avaliado em nu´mero naturais, vamos mostrar agora
a volta, se temos todos os valores do polinoˆmio avaliados nos naturais divisı´veis por
k enta˜o as condic¸o˜es iniciais, sa˜o divisı´veis por k, essa proposic¸a˜o e´ trivial , pois se
para todos naturais o polinoˆmio tem resultado divisı´vel por k, enta˜o em especial, os
valores iniciais, tambe´m sera˜o divisı´veis por k.
ê Demonstrac¸a˜o. Seja uma func¸a˜o do tipo
f(n) =
p∑
k=1
ck(ak)
n
com valores ak distintos entre si , para cada k, sua recorreˆncia sera´ uma da forma
p∏
k=1
(E− ak)f(n) = 0
(considerando tambe´m que a recorreˆncia quando expandida, tenha coeficientes intei-
ros) de grau p temos que ter enta˜o p condic¸o˜es iniciais, se elas todas forem ≡ 0modk,
temos que a func¸a˜o f(n) sera´ ≡ 0modk para todo n
CAPI´TULO 1. RECORREˆNCIAS, SOMATO´RIOS E DIVISIBILIDADE 5
ê Demonstrac¸a˜o. Passando a recorreˆncia em zk, temos que todos os termos
provenientes da recorreˆncia sera˜o equivalentes a zero, a volta e´ verdadeira tambe´m,
pois se a func¸a˜o f(n), tiver todos os termos divisı´veis por k, quando n e´ natural, ela
tera´ as condic¸o˜es iniciais divisı´veis por k.
Aplicac¸o˜es. Primeiro temos que com isso e´ possı´vel demonstrar teoremas de
divisibilidade de func¸o˜es atraveˆs de computador, pois para uma recorreˆncia de grau
p precisamos testar se p nu´meros sa˜o divisı´veis por um nu´mero k, para que a
func¸a˜o nos naturais seja divisı´vel por k. Segundo podemos escrever infinitas func¸o˜es
que sejam sempre divisı´veis por um valor que queremos, essa implicac¸a˜o nos da
possibilidade de criar exemplos de problemas com divisibilidade.
Em geral se temos todas as constantes iniciais de uma recorreˆncia homogeˆnea
de coeficientes inteiros equivalentes a zero em Zk, enta˜o a func¸a˜o que satisfaz essa
recorreˆncia e´ divisı´vel por k para todo n natural.
Z Exemplo 1. Mostre que n3+2n e´ divisı´vel por 3 para todo n natural. Temos
que testar os 4 primeiros termos pela func¸a˜o ser do grau 3
f(0) = 0 f(1) = 3 f(2) = 12 f(3) = 33
como todos 4 primeiros sa˜o divisı´veis por 3 enta˜o a func¸a˜o em n toma sempre
valores divisı´veis por 3.
Z Exemplo 2. Prove que n3+5n e´ divisı´vel por 6 para todo n natural. Testamos
as 4 condic¸o˜es iniciais f(0) = 0, f(1) = 6, f(2) = 18, f(3) = 42, enta˜o a proposic¸a˜o
e´ verdadeira.
Z Exemplo 3. Mostrar que f(n) = n
3
3
+
n2
2
+
n
6
sempre retorna valores inteiros.
Vale f(0) = 0, f(1) = 1, f(2) = 5 e f(3) = 14, implicando que a func¸a˜o sempre
retorna valores inteiros.
CAPI´TULO 1. RECORREˆNCIAS, SOMATO´RIOS E DIVISIBILIDADE 6
F Teorema 1. Se f(x) e´ um polinoˆmio de grau p que assume valores divisı´veis
por k para todo n natural, enta˜o
∆sf(x0) ≡ 0 mod k
para todo s e x0 naturais.
ê Demonstrac¸a˜o. Se f(x) e´ um polinoˆmio que assume valores divisı´veis por k
quando x natural, temos
k|f(x0)⇐⇒ f(x0) = kg(x0)
com g(x0) inteiro,logo em Zk a func¸a˜o assume valores sempre iguais a zero, logo
suas diferenc¸as devem ser todas iguais a zero. Podemos ver isso de outra maneira
fazendo
∆sf(x0) = ∆
skg(x0) = k∆
sg(x0) ≡ 0 mod k
ou expandindo
∆sf(x0) =
s∑
l=0
(
s
l
)
(−1)s−lf(x0 + l)
como todo f(x0 + l) com l variando de 0 ate´ s um natural, e´ divisı´vel por k, podemos
escrever
∆sf(x0) =
s∑
l=0
(
s
l
)
(−1)s−lkg(x0 + l) = k.
s∑
l=0
(
s
l
)
(−1)s−lg(x0 + l)
passando no anel Zk temos essa somato´rio equivalente a zero.
Outra demonstrac¸a˜o pode ser dada pela func¸a˜o geradora.
G(n) =
p∑
k=0
k−1∑
n=0
akf(n)x
n+p−k
p∑
k=0
akxp−k
ê Demonstrac¸a˜o. Se uma recorreˆncia de ordem p tem todas suas p condic¸o˜es
iniciais divisı´veis por s, podemos escrever f(n) = p.g(n), para n entre 0 e p− 1, com
g(n) inteiro para esses mesmo valores. Podemos enta˜o substituir essa igualdade na
func¸a˜o geradora
G(n) =
p∑
k=0
k−1∑
n=0
akp.g(n)x
n+p−k
p∑
k=0
akxp−k
CAPI´TULO 1. RECORREˆNCIAS, SOMATO´RIOS E DIVISIBILIDADE 7
como p e´ uma constante ela pode sair do somato´rio, pela propriedades do so-
mato´rio
G(n) = p.
p∑
k=0
k−1∑
n=0
akg(n)x
n+p−k
p∑
k=0
akxp−k
e como
p.
p∑
k=0
k−1∑
n=0
akg(n)x
n+p−k
p∑
k=0
akxp−k
gera uma sequeˆncia de nu´meros inteiros (pois as condic¸o˜es iniciais sa˜o inteiras) com
coeficientes constantes dada pela func¸a˜o geradora, fica demonstrada a propriedade
de divisibilidade.
1.2 Somato´rios e divisibilidade
Sabemos que a soma de nu´meros inteiros e´ um nu´mero inteiro, vamos usar esse
fato para provar que certas expresso˜es resultam em nu´meros inteiros e propriedades
de divisibilidade
b∑
k=a
ck =
ck
c− 1
∣∣∣∣b+1
a
=
cb+1 − ca
c− 1
com c 6= 1 um nu´mero inteiro, chegamos a conclusa˜o enta˜o que a− 1 divide cb+1 − ca
se a,b e c 6= 1 sa˜o inteiros e b ≥ a.
Z Exemplo 4. Provar que 6|(n)(n+ 1)(n+ 2) . Temos que
n∑
k=1
k =
k(2,1)
2
∣∣∣∣n+1
1
=
k(k− 1)
2
∣∣∣∣n+1
1
=
(n+ 1)(n)
2
e´ soma de inteiros logo e´ inteiro, aplicando somato´rio mais uma vez, na expressa˜o
(k+ 1)(k)/2 = (k+ 1)(2,1)/2
n∑
k=1
(k+ 1)(2,1)
2
=
(k+ 1)(3,1)
6
∣∣∣∣n+1
1
=
(k+ 1)(3,1)
6
=
(n+ 2)(n+ 1)(n)
6
CAPI´TULO 1. RECORREˆNCIAS, SOMATO´RIOS E DIVISIBILIDADE 8como e´ soma de nu´mero inteiros, enta˜o e´ um nu´mero inteiro, logo 6|(n + 2)(n +
1)(n).
Z Exemplo 5. Mostrar que n7 −n e´ divisı´vel por 7 para todo n inteiro, vamos
achar um somato´rio cujo resultado seja n
7 − n
7
n∑
k=1
f(k) =
n7 − n
7
enta˜o aplicando ∆ em ambos lados segue
f(n+ 1) = (∆n
7) − 1
7
∆n7 = (n+ 1)7 − n7 = 1 + 7n+ 21n2 + 35n3 + 35n4 + 21n5 + 7n6
logo
f(n+ 1) = n+ 3n2 + 5n3 + 5n4 + 3n5 + n6
como temos f(k+ 1) = ∆k
7 − k
7
segue que aplicando a soma com k variando de 0
ate´ n− 1 que
n−1∑
k=0
f(k+ 1) =
n−1∑
k=0
∆
k7 − k
7
=
k7 − k
7
∣∣∣∣n
0
=
n7 − n
7
assim f(k+1) tem coeficientes inteiros e seu somato´rio que e´ n
7 − n
7
sera´ soma
de nu´meros inteiros, sendo que a soma de nu´meros inteiros e´ tambe´m um nu´mero
inteiro segue que n
7 − n
7
e´ inteiro para todo n natural, para ver o caso para n
inteiro negativo basta ver que a func¸a˜o e´ ı´mpar.
b Propriedade 2. Seja uma func¸a˜o g de N em R. Se ∆g(n) e´ uma func¸a˜o que
admite valor inteiro para todo n natural e g(a) = 0, para algum a natural, enta˜o
g(n) assume valor inteiro para todo n natural.
ê Demonstrac¸a˜o. Seja
n∑
k=0
f(k) = g(n)
CAPI´TULO 1. RECORREˆNCIAS, SOMATO´RIOS E DIVISIBILIDADE 9
enta˜o
∆g(n) = f(n+ 1), ∆g(k) = f(k+ 1)
pela hipo´tese tem-se que f(k+ 1) admite valor inteiro para todo k natural, aplicamos
a soma enta˜o com k variando de k = a ate´ k = n− 1, daı´ segue
n−1∑
k=a
f(k+ 1) =
n−1∑
k=a
∆g(k) = g(k)
∣∣∣∣n
a
= g(n) − g(a)︸︷︷︸
=0
= g(n)
isso para n − 1 ≥ a, n ≥ a + 1, nesse caso g(n) sera´ somato´rio de valores inteiros,
logo um nu´mero inteiro, para todo n nessas condic¸o˜es. Caso a − 1 ≥ n, tomando a
soma com k variando de k = n ate´ a− 1 segue
a−1∑
k=n
f(k+ 1) =
a−1∑
k=n
∆g(k) = g(k)
∣∣∣∣a
n
= g(a)︸︷︷︸
=0
−g(n) = −g(n)
nesse caso novamente temos que g(n) e´ inteiro, por ser soma de inteiros, o caso que
falta e´ para n = a que e´ inteiro pois g(a) = 0.
$ Corola´rio 1 (Pequeno teorema de Fermat). Vamos mostrar que np − n
p
e´
inteiro para p primo e para todo n inteiro. Temos
∆
np − n
p
=
∆np − 1
p
mas
∆np = (n+ 1)p − np =
p∑
k=0
(
p
k
)
nk − np =
p−1∑
k=0
(
p
k
)
nk, ∆np − 1 =
p−1∑
k=1
(
p
k
)
nk
daı´ segue que ∆n
p − n
p
e´ polinoˆmio de coeficientes inteiros, pois p|
(
p
k
)
com
1 ≤ k ≤ p − 1 e ainda temos 1
p − 1
p
= 0, logo pelo resultado anterior tem-se que
np − n
p
= g(n) e´ inteiro para todo n natural. Se p > 2, p e´ ı´mpar logo a func¸a˜o
e´ ı´mpar e tem-se que g(n) e´ divisı´vel por p para todo n inteiro, se p = 2 temos
g(−n) =
n2 + n
2
=
n(n+ 1)
2
que tambe´m e´ inteiro pois 2|n ou 2|n + 1, logo esta´
provado.
CAPI´TULO 1. RECORREˆNCIAS, SOMATO´RIOS E DIVISIBILIDADE 10
b Propriedade 3. Se a e´ inteiro enta˜o (a+ 1)n − 1 e´ divisı´vel por a.
ê Demonstrac¸a˜o. Seja f(n) = (a+ 1)
n − 1
a
enta˜o f(0) = (a+ 1)
0 − 1
a
=
1 − 1
a
= 0
e temos ∆f(n) = a(a+ 1)
n
a
= (a + 1)n que e´ inteiro para todo n natural, logo f(n)
assume sempre valores inteiros enta˜o (a+ 1)n − 1 e´ divisı´vel por a.
Z Exemplo 6. Mostrar que
10n+1 − 10 − 9n
e´ divisı´vel por 81.
Seja f(n) = 10
n+1 − 10 − 9n
81
temos f(0) = 10 − 10
81
= 0 e ∆f(n) = 10
n+1 − 1
9
que
e´ sempre inteiro, logo da propriedade demonstrada segue o resultado.
1.3 Recorreˆncias e nu´meros primos entre si
F Teorema 2. Seja uma recorreˆncia do tipo f(n + 2) = cf(n + 1) + f(n), com c
um nu´mero inteiro, se as condic¸o˜es iniciaisf(0) e f(1) sa˜o primas entre si, enta˜o
f(n) e f(n+ 1) sa˜o primos entre si, para todo n natural.
ê Demonstrac¸a˜o. Demonstrac¸a˜o por induc¸a˜o, os dois primeiros nu´meros ja´ sa˜o
primos entre si, vamos considerar agora que f(n) e f(n+ 1), sejam primos entre si, e
provar que f(n + 1) e f(n + 2) sa˜o primos entre si, como f(n) e f(n + 1), sa˜o primos
entre si, enta˜o existem inteiros a e b tais que
af(n+ 1) + bf(n) = 1
por hipo´tese, vamos provar agora que existem constantes a ′ e b ′ tais que
b ′f(n+ 2) + a ′f(n+ 1) = 1
, para isso tome b ′ = b e a ′ = a− bc dai temos
bf(n+ 2) + (a− bc)f(n+ 1) = bf(n+ 2) + af(n+ 1) − bcf(n+ 1) =
CAPI´TULO 1. RECORREˆNCIAS, SOMATO´RIOS E DIVISIBILIDADE 11
como temos por definic¸a˜o da sequeˆncia f(n+2) = cf(n+1)+f(n), substituindo temos
= bcf(n+ 1) + bf(n) + af(n+ 1) − bcf(n+ 1) = af(n+ 1) + bf(n) = 1
que e´ igual a 1 pela hipo´tese da induc¸a˜o.
F Teorema 3. Seja uma recorreˆncia do tipo f(n + 2) = cf(n + 1) − f(n), com c
um nu´mero inteiro, se as condic¸o˜es iniciaisf(0) e f(1) sa˜o primas entre si, enta˜o
f(n) e f(n+ 1) sa˜o primos entre si, para todo n natural.
ê Demonstrac¸a˜o. Demonstrac¸a˜o por induc¸a˜o, os dois primeiros nu´meros ja´ sa˜o
primos entre si, vamos considerar agora que f(n) e f(n+ 1), sejam primos entre si, e
provar que f(n + 1) e f(n + 2) sa˜o primos entre si, como f(n) e f(n + 1), sa˜o primos
entre si, enta˜o existem inteiros a e b tais que
af(n+ 1) + bf(n) = 1
por hipo´tese, vamos provar agora que existem constantes a ′ e b ′ tais que
b ′f(n+ 2) + a ′f(n+ 1) = 1
, para isso tome b ′ = −b e a ′ = a+ bc dai temos
−bf(n+ 2) + (a+ bc)f(n+ 1) = −bf(n+ 2) + af(n+ 1) + bcf(n+ 1) =
como temos por definic¸a˜o da sequeˆncia f(n+2) = cf(n+1)−f(n), substituindo temos
= −bcf(n+ 1) + bf(n) + af(n+ 1) + bcf(n+ 1) = af(n+ 1) + bf(n) = 1
que e´ igual a 1 pela hipo´tese da induc¸a˜o.
1.4 Um resultado sobre nu´meros primos
Vamos responder a questa˜o, existe uma func¸a˜o polinomial p(x) que quando ava-
liada nos nu´meros naturais gere todos os nu´meros primos em sequeˆncia?1. Vamos
comec¸ar enta˜o com um lema que vai nos ajudar na demonstrac¸a˜o
1Nesse caso estou considerando que f(0) = 2, f(1) = 3,...,f(n) = p(n + 1) onde p(n) e´ o n-e´simo
primo.
CAPI´TULO 1. RECORREˆNCIAS, SOMATO´RIOS E DIVISIBILIDADE 12
♣ Lema 1.
(
2n
n
)
e´ sempre divisı´vel por 2.
ê Demonstrac¸a˜o. Por relac¸a˜o de Stiefel temos(
2n
n
)
=
(
2n− 1
n
)
+
(
2n− 1
n− 1
)
mas temos (
2n− 1
n
)
=
(2n− 1)!
n!(2n− 1 − n)!
=
(2n− 1)!
n!(n− 1)!(
2n− 1
n− 1
)
=
(2n− 1)!
(n− 1)!(2n− 1 − n+ 1)
=
(2n− 1)!
(n− 1)!(n!)
logo temos (
2n− 1
n− 1
)
=
(
2n− 1
n
)
assim (
2n
n
)
= 2
(
2n− 1
n
)
sendo
(
2n− 1
n
)
um nu´mero inteiro, temos que
(
2n
n
)
e´ mu´ltiplo de 2.
Agora seja um polino´mio de grau p, f(x), temos que
∆p+1f(x) = 0 = (E− 1)p+1f(x) =
p+1∑
k=0
(
p+ 1
k
)
(−1)p+1−kf(x+ k) = 0
abrindo o primeiro e u´ltimo termo, temos
p+1∑
k=0
(
p+ 1
k
)
(−1)p+1−kf(x+ k) =
=
(
p+ 1
p+ 1
)
(−1)p+1−p−1f(x+p+1)+
p∑
k=1
(
p+ 1
k
)
(−1)p+1−kf(x+k)+
(
p+ 1
0
)
(−1)p+1f(x) =
= f(x+ p+ 1) +
p∑
k=1
(
p+ 1
k
)
(−1)p+1−kf(x+ k) + (−1)p+1f(x) = 0
tome agora o caso especial x = 0
f(p+ 1) +
p∑
k=1
(
p+ 1
k
)
(−1)p+1−kf(k) + (−1)p+1f(0) = 0
e com a condic¸a˜o inicial f(0) um nu´mero divisı´vel por 2
f(p+ 1) +
p∑
k=1
(
p+ 1
k
)
(−1)p+1−kf(k) + (−1)p+12k = 0
CAPI´TULO 1. RECORREˆNCIAS, SOMATO´RIOS E DIVISIBILIDADE 13
sejam agora todas as outras constantes iniciais (de f(1) ate´ f(p) deixando resto 1 na
divisa˜o por 2, assim temos f(k) = 2g(k) + 1 onde g(k) e´ inteiro para todo k de 1 ate´
p. Agora se p+ 1 e´ ı´mpar, p e´ um nu´mero par, abrindo o somato´rio vemos que temos
um nu´mero par de termos multiplicados pelos coeficiente binomiais 2
f(p+1)+
(
p+ 1
1
)
(−1)p+1−1f(1)+
(
p+ 1
2
)
(−1)p+1−2f(2)+ ...+
(
p+ 1
p− 1
)
(−1)p+1−2f(p−1)+
+
(
p+ 1
p
)
(−1)p+1−pf(p) + (−1)p+12k = 0
como temos a propriedade do coeficiente binomial(
p+ 1
k
)
=
(
p+ 1
p+ 1 − k
)
=
(p+ 1)!
(p+ 1 − k)!(k)!logo (
p+ 1
1
)
=
(
p+ 1
p
)
(
p+ 1
2
)
=
(
p+ 1
p− 1
)
...
podemos colocar esses coeficientes binomiais iguais em evideˆncia, a soma fica
f(p+1)+
(
p+ 1
1
)(
(−1)p+1−1f(1)+(−1)p+1−pf(p)
)
+
(
p+ 1
2
)(
(−1)p+1−2f(2)+(−1)p+1−2f(p−1)
)
+
...+ (−1)p+12k = 0
como os nu´meros f(1) e f(p), f(2) e f(p− 1),..., deixam todos resto 1 na divisa˜o por 2,
sua soma ou subtrac¸a˜o deixa resto zero na divisa˜o por 2 e como
(
p+ 1
k
)
e´ sempre
inteiro, temos todo o somato´rio um nu´mero inteiro divisı´vel por 2, logo f(p+ 1) deve
ser divisı´vel por 2
f(p+ 1) = −
(
p+ 1
1
)(
(−1)p+1−1f(1) + (−1)p+1−pf(p)
)
︸ ︷︷ ︸
divisivelpor2
−
2pois temos coeficientes binomiais de
(
p+ 1
1
)
ate´
(
p+ 1
p
)
sendo p termos, como p+ 1 e´ ı´mpar, p
e´ par, logo temos um nu´mero par de termos.
CAPI´TULO 1. RECORREˆNCIAS, SOMATO´RIOS E DIVISIBILIDADE 14
(
p+ 1
2
)(
(−1)p+1−2f(2) + (−1)p+1−2f(p− 1)
)
︸ ︷︷ ︸
divisivelpor2
...− (−1)p+12k
Agora se p+ 1 e´ par em
f(p+1)+
(
p+ 1
1
)
(−1)p+1−1f(1)+
(
p+ 1
2
)
(−1)p+1−2f(2)+ ...+
(
p+ 1
p− 1
)
(−1)p+1−2f(p−1)+
+
(
p+ 1
p
)
(−1)p+1−pf(p) + (−1)p+12k = 0
temos p um nu´mero ı´mpar, pela simetria dos coeficientes binomiais, teremos um
termo central
(
p+ 1
(p+1)
2
)
que e´ sempre divisı´vel por 2 pelo lema, o somato´rio fica enta˜o
algo do tipo
f(p+ 1) +
(
p+ 1
1
)
(−1)p+1−1f(1) +
(
p+ 1
2
)
(−1)p+1−2f(2) + ...
(
p+ 1
(p+1)
2
)
cp+
+
(
p+ 1
p− 1
)
(−1)p+1−2f(p− 1) +
(
p+ 1
p
)
(−1)p+1−pf(p) + (−1)p+12k = 0
e os termos restantes tem soma divisı´vel por 2 pelo mesmo argumento dado no caso
de quando p+ 1 e´ ı´mpar.
$ Corola´rio 2. No caso de uma func¸a˜o polinomial gerando primos , temos
f(0) = 2 e todas outras condic¸o˜es iniciais ı´mpares, pois o 2 e´ o u´nico primo par
e´ 2, logo havera´ um termo divisı´vel por 2 em f(p + 1), enta˜o na˜o ha´ polino´mios
que gerem sempre primos dessa maneira.
1.5 Interpolac¸a˜o e divisibilidade
Se um polinoˆmio f(n) e´ de grau p podemos escrever pela interpolac¸a˜o
f(n) =
p∑
k=0
(
n
k
)
∆kf(0).
Se s|f(k) para k de 0 ate´ p enta˜o o polinoˆmio sempre ira´ retornar valores divisı´veis
por s. Pois
∆nf(0) =
n∑
k=0
(
n
k
)
(−1)n−kf(k)
depende apenas de f(k) de k = 0 ate´ no ma´ximo p em ∆pf(0).
CAPI´TULO 1. RECORREˆNCIAS, SOMATO´RIOS E DIVISIBILIDADE 15
Z Exemplo 7. Mostrar que 30|n5 − n.
Temos f(−2) = −30, f(−1) = 0, f(0) = 0, f(1) = 0, f(2) = 30, f(3) = 240 todos
sa˜o mu´ltiplos de 30, sendo 6 pontos para um polinoˆmio de grau 5 enta˜o 30|n5−n
para todo n .
	Recorrências, somatórios e divisibilidade
	Recorrência e divisibilidade
	Somatórios e divisibilidade
	Recorrências e números primos entre si
	Um resultado sobre números primos
	Interpolação e divisibilidade