Problemas Teoremas

Abril 16, 2012

Relação de recorrência linear homogénea de 2.ª ordem com coeficientes constantes

Filed under: Matemática,Matemática Discreta,Mathematics Stack Exchange,Recorrência — Américo Tavares @ 12:25 am
Tags: ,

Numa questão de optimus, no Mathematics Stack Exchange pede-se a determinação da solução de

a_{n}-a_{n-1}-2a_{n-2}=0,\qquad a_0=2,a_1=4

A tradução da minha resposta é esta:

A recorrência/equação com diferenças homogénia de 2.ª ordem com coeficientes constantes

x_{n}+c_{1}x_{n-1}+c_{2}x_{n-2}=0\qquad (1)

tem duas soluções fundamentais (\lambda _{1}^{n})_{n\geq 0} e (\lambda_{2}^{n})_{n\geq 0}, em que \lambda _{1},\lambda _{2} são os zeros do polinómio característico

\lambda ^{2}+c_{1}\lambda +c_{2}\qquad (2)

Confirmemos.

\begin{aligned}\lambda _{1}^{n}+c_{1}\lambda _{1}^{n-1}+c_{2}\lambda _{1}^{n-2}&=\lambda_{1}^{n-2}\left( \lambda _{1}^{2}+c_{1}\lambda _{1}+c_{2}\right) \equiv 0\\ &\\\lambda _{2}^{n}+c_{1}\lambda _{2}^{n-1}+c_{2}\lambda _{2}^{n-2}&=\lambda_{2}^{n-2}\left( \lambda _{2}^{2}+c_{2}\lambda _{2}+c_{2}\right)\equiv 0\end{aligned}

Se \lambda _{1}\neq \lambda _{2} a solução geral de (1) é a combinação linear de \lambda _{1}^{n} e \lambda _{2}^{n}

x_{n}=A\lambda _{1}^{n}+B\lambda _{2}^{n}\qquad (3)

como pode confirmar substituindo (3) em (1). Apliquemos este resultado a equação com diferenças a_{n}-a_{n-1}-2a_{n-2}=0. O polinómio característico \lambda ^{2}-\lambda -2 tem os zeros \lambda_{1}=-1,\lambda _{2}=2.

Logo (3) fica

a_{n}=A(-1)^{n}+B2^{n}

As constantes A and B determinam-se usando as condições iniciais a_{0}=2, a_{1}=4:

a_{0}=A(-1)^{0}+B2^{0}=A+B=2\Leftrightarrow B=2-A

Assim

a_{n}=A(-1)^{n}+\left( 2-A\right) 2^{n}

e

a_{1}=A(-1)^{1}+\left( 2-A\right) 2^{1}=-A+4-2A=-3A+4=4\Leftrightarrow A=0.

Uma vez que A=0 e B=2-A=2 a solução é

a_{n}=2\cdot 2^{n}=2^{n+1}\qquad n\geq 2.

Julho 8, 2011

Resolução da relação de recorrência T(n) = 3T(n-2) + 9, T(1) = T(2) = 1

Filed under: Exercícios Matemáticos,Matemática,Matemática Discreta,Problemas,Recorrência — Américo Tavares @ 7:15 pm
Tags: , ,

Mais uma vez publico aqui a tradução de uma resposta a uma questão no MSE. Desta vez trata-se da resolução da relação de recorrência

T(n)=3T(n-2)+9,\qquad T(1)=T(2)=1

pedida por Nir nesta questão. Apliquei a ideia fundamental indicada num comentário de Ross Millikan. Inicialmente enganei-me na resolução, fui alertado para o erro por user6312 e refi-la.

Os primeiros termos são:

\begin{aligned}T(1) &=T(2)=U(1)=1 \\T(3)&=T(4)=U(2)=12 \\T(5) &=T(6)=U(3)=45 \\&\cdots\end{aligned}

Generalizando, tem-se

T(2n-1)=T(2n)=U(n),\qquad n\ge 1.\qquad (1)

Dado que

T(2n-1)=3T(2n-3)+9=3T(2n-2)+9,

obtemos

U(1)=1,\qquad U(n)=3U(n-1)+9,\qquad n\ge 2.\qquad (2)

Vamos aplicar rudimentos da teoria das recorrências  (ou equações com diferenças, ver por ex. An introduction to difference equations de Saber Elaydi.) Esta relação de recorrência é não homogénea,  pelo que teremos de determinar uma solução particular da recorrência e resolver a recorrência homogénea, que é linear e tem coeficientes constantes . Assim, a solução explícita é da forma

U(1)=1,\qquad U(n)=AX^{n}+C,\qquad (3)

em que X é a raíz da equação característica X-3=0 associada à equação homogénea U(n)-3U(n-1)=0 e C é uma solução particular (neste caso, constante) de U(n)=3U(n-1)+9. De (2), deverá ser C=3C-9, isto é, C=-9/2. Assim U(n)=3^{n}A-9/2.

Da condição inicial U(1)=1, obtemos 1=3A-9/2, donde A=11/6. Por conseguinte a solução de (2) é

U(n)=\dfrac{11}{6}3^{n}-\dfrac{9}{2},\qquad n\ge 1\qquad (4)

Logo a solução da recorrência dada T(n)=3T(n-2)+9 é

T(2n-1)=T(2n)=U(n)=\dfrac{11}{6}3^{n}-\dfrac{9}{2},\qquad n\ge 1.\qquad (5)

Bibliografia (em português)

ANDRÉ, Carlos e FERREIRA, Fernando, Matemática Finita, Universidade Aberta, nº 203, Lisboa, 2000.

Maio 25, 2011

Determinação dos valores da função zeta nos pares através de uma série de Fourier

Filed under: Análise de Fourier,Cálculo,Exercícios Matemáticos,Matemática,Recorrência,Séries — Américo Tavares @ 11:14 pm
Tags: ,

Para obter valores de \zeta(2p), como exercício de Cálculo, retomo a integração por partes da entrada Relações de recorrência geradas pela integração por partes, em particular a última relação de recorrência que vou justificar. Considero a função par  f(x)=x^{2p} no intervalo \left[ -\pi ,\pi \right] e vou determinar a sua série trigonométrica de Fourier. Como é sabido esta série converge para uma função periódica, que é a repetição de f(x) em todo o eixo real (ver figura).

x^{2p}\sim\dfrac{a_{0,2p}}{2}+\displaystyle\sum_{n=1}^{\infty }\left( a_{n,2p}\cos nx+b_{n,2p}\sin nx\right)

em que os coeficientes a_{n,2p} são dados pelas expressões

a_{0,2p}=\dfrac{1}{\pi}\displaystyle\int_{-\pi }^{\pi }x^{2p}\;\mathrm{d}x=\frac{1}{\pi }\dfrac{2\pi ^{2p+1}}{2p+1}=\dfrac{2\pi ^{2p}}{2p+1}

a_{n,2p}=\dfrac{1}{\pi }\displaystyle\int_{-\pi }^{\pi }x^{2p}\cos nx\;\mathrm{d}x=\dfrac{2}{\pi }\displaystyle\int_{0}^{\pi }x^{2p}\cos nx\;\mathrm{d}x\qquad n\geq 1

e os coeficientes b_{n,2p} são nulos, em virtude de f(x)\sin nx=x^{2n}\sin nx ser uma função ímpar:

b_{n,2p}=\dfrac{1}{\pi }\displaystyle\int_{-\pi }^{\pi }x^{2p}\sin nx\;\mathrm{d}x=0\qquad n\geq 1

Assim, teremos

x^{2p}=\dfrac{\pi ^{2p}}{2p+1}+\dfrac{2}{\pi }\displaystyle\sum_{n=1}^{\infty }\cos nx\int_{0}^{\pi }x^{2p}\cos nx\;\mathrm{d}x

e para f(\pi )=\pi ^{2p}

\begin{aligned}\pi ^{2p} &=\dfrac{\pi ^{2p}}{2p+1}+\dfrac{2}{\pi }\displaystyle\sum_{n=1}^{\infty }\cos n\pi\displaystyle\int_{0}^{\pi }x^{2p}\cos nx\;\mathrm{d}x \\ &=\dfrac{\pi ^{2p}}{2p+1}+\dfrac{2}{\pi }\displaystyle\sum_{n=1}^{\infty }\cos n\pi \cdot I_{n,2p}\end{aligned}

em que I_{n,2p} é  o integral

I_{n,2p}=\displaystyle\int_{0}^{\pi }x^{2p}\cos nx\;\mathrm{d}x

Para o integrar, por partes, escolho f(x)=x^{2p} e g^{\prime }(x)=\cos nx, pelo que f^{\prime }(x)=2px^{2p-1} e g(x)=\dfrac{1}{n}\sin nx; resulta

\begin{aligned}\displaystyle\int f(x)g^{\prime }(x)\;\mathrm{d}x&=f(x)g(x)-\displaystyle\int f^{\prime }(x)g(x)\;\mathrm{d}x\\\displaystyle\int x^{2p}\cos nx\;\mathrm{d}x&=\dfrac{1}{n}x^{2p}\sin nx-\dfrac{2p}{n}\displaystyle\int x^{2p-1}\sin nx\;\mathrm{d}x\end{aligned}

Integrando novamente por partes, com f(x)=x^{2p-1} e g^{\prime }(x)=\sin nx, sendo, portanto, f^{\prime }(x)=\left( 2p-1\right) x^{2\left( p-1\right) } e g(x)=\int\sin \left( nx\right) dx=-\dfrac{\cos nx}{n}, vem

\begin{aligned}\displaystyle\int f(x)g^{\prime }(x)\;\mathrm{d}x&=f(x)g(x)-\displaystyle\int f^{\prime }(x)g(x)\;\mathrm{d}x \\\displaystyle\int x^{2p-1}\sin nx\;\mathrm{d}x &=-\dfrac{1}{n}x^{2p-1}\cos nx+\dfrac{2p-1}{n}\displaystyle\int x^{2\left( p-1\right) }\cos nx\;\mathrm{d}x\end{aligned}

e, por isso,

\displaystyle\int x^{2p}\cos nx\;\mathrm{d}x=\dfrac{1}{n}x^{2p}\sin nx-\dfrac{2p}{n}\displaystyle\int x^{2p-1}\sin nx\;\mathrm{d}x

\begin{aligned}&=\dfrac{1}{n}x^{2p}\sin nx-\dfrac{2p}{n}\left( -\dfrac{1}{n}x^{2p-1}\cos nx+\dfrac{2p-1}{n}\displaystyle\int x^{2\left( p-1\right) }\cos nx\;\mathrm{d}x\right) \\&=\dfrac{1}{n}x^{2p}\sin nx+\dfrac{2p}{n^{2}}x^{2p-1}\cos nx-\dfrac{2p\left( 2p-1\right) }{n^{2}}\displaystyle\int x^{2\left( p-1\right) }\cos nx\;\mathrm{d}x\end{aligned}

donde

\displaystyle\int_{0}^{\pi }x^{2p}\cos nx\;\mathrm{d}x=\dfrac{2p}{n^{2}}\pi ^{2p-1}\cos n\pi -\dfrac{2p\left( 2p-1\right) }{n^{2}}\displaystyle\int_{0}^{\pi }x^{2\left( p-1\right) }\cos nx\;\mathrm{d}x

Ou seja, vemos que I_{n,2p} verifica a relação de recorrência

I_{n,2p}=\dfrac{2p}{n^{2}}\pi ^{2p-1}\cos n\pi -\dfrac{2p\left( 2p-1\right) }{n^{2}}I_{n,2\left( p-1\right) }\qquad I_{n,0}=0\qquad(\ast)

que deixei como exercício na entrada referida.

Para p=1, como

I_{n,2}=\dfrac{2}{n^{2}}\pi \cos n\pi

temos

\begin{aligned}\pi ^{2} &=\dfrac{\pi ^{2}}{3}+\dfrac{2}{\pi }\displaystyle\sum_{n=1}^{\infty }\cos n\pi\cdot I_{n,2} \\&=\dfrac{\pi ^{2}}{3}+\dfrac{2}{\pi }\displaystyle\sum_{n=1}^{\infty }\cos n\pi \left(\dfrac{2}{n^{2}}\pi \cos n\pi \right) \\ &=\dfrac{\pi ^{2}}{3}+4\displaystyle\sum_{n=1}^{\infty }\dfrac{1}{n^{2}} \end{aligned}

donde

\zeta (2)=\displaystyle\sum_{n=1}^{\infty }\dfrac{1}{n^{2}}=\dfrac{1}{6}\pi ^{2}

e para p=2, atendendo a que

\begin{aligned}I_{n,4} &=\dfrac{4}{n^{2}}\pi ^{3}\cos n\pi -\dfrac{12}{n^{2}}I_{n,2} \\&=\left( \dfrac{4}{n^{2}}\pi ^{3}-\dfrac{24\pi }{n^{4}}\right) \cos n\pi\end{aligned}

vem

\begin{aligned}\pi ^{4} &=\dfrac{\pi ^{4}}{5}+\dfrac{2}{\pi }\displaystyle\sum_{n=1}^{\infty }\cos n\pi\cdot I_{4} \\&=\dfrac{\pi ^{4}}{5}+\dfrac{4\pi ^{4}}{3}-48\displaystyle\sum_{n=1}^{\infty }\dfrac{1}{n^{4}}\end{aligned}

pelo que

\zeta (4)=\displaystyle\sum_{n=1}^{\infty }\dfrac{1}{n^{4}}=\dfrac{1}{90}\pi ^{4}

Da mesma forma obteríamos

\begin{aligned}I_{n,6} &=\dfrac{6}{n^{2}}\pi ^{5}\cos n\pi -\dfrac{30}{n^{2}}\left( \dfrac{4}{n^{2}}\pi ^{3}-\dfrac{24\pi }{n^{4}}\right) \cos n\pi \\&=\left( \frac{6}{n^{2}}\pi ^{5}-\dfrac{120}{n^{4}}\pi ^{3}+\dfrac{720\pi }{n^{6}}\right) \cos n\pi \end{aligned}

e

\pi ^{6}=\dfrac{\pi ^{6}}{7}+2\displaystyle\sum_{n=1}^{\infty }\left( \dfrac{6}{n^{2}}\pi^{4}-\dfrac{120}{n^{4}}\pi ^{2}+\dfrac{720}{n^{6}}\right)

donde, substituindo os resultados já calculados de \zeta (2) e \zeta (4)

\zeta (6)=\displaystyle\sum_{n=1}^{\infty }\dfrac{1}{n^{6}}=\dfrac{1}{945}\pi ^{6}

E, em geral, poderíamos determinar \zeta (2p) através da relação de recorrência de I_{n,2p}, o que se traduz em ir calculando
sucessivamente I_{n,2},I_{n,4},\ldots ,I_{n,2p-2} e \zeta (2),\zeta (4),\ldots,\zeta (2p-2).

Exemplo gráfico para 2p=6

Figura: Função periódica definida em \left[ -\pi ,\pi \right] por f(x)=x^{6} (a azul) e a soma parcial dos primeiros 10 termos do seu desenvolvimento em série de Fourier (a vermelho)

\dfrac{\pi ^{6}}{7}+\dfrac{2}{\pi }\displaystyle\sum_{n}^{}\left( \left( \dfrac{6}{n^{2}}\pi ^{5}-\dfrac{120}{n^{4}}\pi ^{3}+\dfrac{720\pi }{n^{6}}\right)\cos n\pi \right) \cos nx

Pondo q=2p, obtemos

\begin{aligned}\pi ^{q} &=\dfrac{\pi ^{q}}{q+1}+\displaystyle\sum_{n=1}^{\infty }\cos n\pi\displaystyle\int_{0}^{\pi}\dfrac{2}{\pi }x^{q}\cos nx\;\mathrm{d}x \\ &=\frac{\pi ^{q}}{q+1}+\displaystyle\sum_{n=1}^{\infty }a_{n,q}\cos n\pi \qquad (q\text{ par})\end{aligned}

ou então, na forma,

\displaystyle\sum_{n=1}^{\infty }a_{n,q}\cos n\pi =\dfrac{q}{q+1}\pi ^{q}\qquad (q\text{ par})

em que

a_{n,q}=\dfrac{2}{\pi }I_{n,q}=\displaystyle\int_{0}^{\pi }\dfrac{2}{\pi }x^{q}\cos nx\;\mathrm{d}x\qquad (q\text{ par})

cumpre a condição, para q par

a_{n,q}=\dfrac{2}{\pi }I_{n,q}=\dfrac{2q}{n^{2}}\pi ^{q-2}\cos n\pi -\dfrac{q\left( q-1\right) }{n^{2}}a_{n,q-2}\qquad a_{n,0}=0\quad(\ast\ast)

Os primeiros termos de a_{n,q} são

\begin{aligned}a_{n,2}&=\left( 4/n^{2}\right) \cos n\pi \\a_{n,4} &=\left( 8\pi^{2}/n^{2}-48/n^{4}\right)\cos n\pi\\a_{n,6}&=\left( 12\pi ^{4}/n^{2}-240\pi^{2}/n^{4}+1440/n^{6}\right)\cos n\pi\\a_{n,8}&=\left( 16\pi ^{6}/n^{2}-672\pi^{4}/n^{4}+13\,440\pi^{2}/n^{6}-80\,640/n^{8}\right)\cos n\pi\end{aligned}

e os da função zeta para valores pares do argumento

\begin{aligned}\zeta (2)/\pi ^{2} &=1/6\qquad \quad \zeta (4)/\pi ^{4}=1/90 \\ \zeta (6)/\pi ^{6} &=1/945\qquad \zeta (8)/\pi ^{8}=1/9450\end{aligned}

A interdependência dos vários \zeta (q), com q par, e a série S_{q}=\sum a_{n,q}\cos n\pi =q\pi ^{q}/\left( q+1\right) , resultante do método de cálculo, é ilustrada por

\begin{aligned}S_{2}&=4\zeta (2)\\S_{4}&=8\left[\pi ^{2}\zeta (2)-6\zeta (4)\right]\\S_{6} &=12\left[ \pi ^{4}\zeta (2)-20\pi ^{2}\zeta (4)+120\zeta (6)\right]\\S_{8} &=16\left[ \pi ^{6}\zeta (2)-42\pi ^{4}\zeta (4)+840\pi ^{2}\zeta(6)-5040\zeta (8)\right]\end{aligned}.

Contudo, não consegui obter uma relação recorrência satisfeita directamente por \zeta (q), muito menos uma fórmula explícita. Mas uma tal fórmula explícita existe e é bem conhecida [1],

\zeta(2p)=(-1)^{p+1}\dfrac{B_{2p}(2\pi)^{2p}}{2(2p)!}

estabelece a relação com os números de Bernoulli B_{p} de ordem par, que podem definir-se pelos coeficientes da série de potências

\dfrac{x}{e^{x}-1}=\displaystyle\sum_{p=0}^{\infty }\dfrac{B_px^{p}}{p!}

ou de forma implícita pela relação de recorrência [2]

\displaystyle\sum_{k=0}^{p}\dbinom{p+1}{k}B_{p}=0,\qquad B_{0}=1.

Quanto à relação de recorrência associada aos valores pares de \zeta(p), Eric Rowland publicou uma, há alguns anos, na web, obtida a partir da integração repetida da parte imaginária do desenvolvimento em série de Taylor de \ln(1-e^{ix}), na vizinhança de x=0.

[28-5-2011, Alterada notação: I_{n,2p} em vez de I_{p} e a_{n,2p},b_{n,2p} em vez de a_{n},b_{n}]

[29-5-2011, Acrescentada relação de recorrência dos números de Bernoulli.]

Bibliografia consultada

[1] EDWARDS, H. M., Rieman’s Zeta Function, Dover Publications, New York, 1974

[2] ANDRÉ, Carlos e FERREIRA, Fernando, Matemática Finita, Universidade Aberta, nº 203, Lisboa, 2000

Abril 18, 2011

Relações de recorrência geradas pela integração por partes

Filed under: Cálculo,Exercícios Matemáticos,Função Gama,Matemática,Matemáticas Gerais,Problemas,Recorrência — Américo Tavares @ 11:03 am
Tags: , ,

Ao utilizar o método de integração por partes, por vezes, chega-se a uma relação de recorrência, o que permite reduzir o cálculo de um integral  ao de outro(s) do mesmo tipo, mas de ordem menor e, por isso, mais simples.  Este método traduz-se, como é sabido, na fórmula

\displaystyle\int f(x)g^{\prime }(x)\;\mathrm{d}x=f(x)g(x)-\displaystyle\int f^{\prime }(x)g(x)\;\mathrm{d}x+C

ou, abreviando para u=f(x) e v=g(x),  na seguinte, mais compacta

\displaystyle\int u\;\mathrm{d}v=uv-\displaystyle\int v\;\mathrm{d}u+C

É conveniente escolher para  g^{\prime }(x) a função mais fácil de integrar, das duas que figuram no produto da função integranda.  Normalmente,  as funções logarítmica, trigonométricas inversas, algébricas, trigonométricas e exponencial (regra prática Liate) apresentam uma facilidade de integração crescente. Mas também requere  um certo artifício, como se pode ver, desde logo, com a primitivação, por partes, de \log x=1\cdot\log x, em que se escolhe para função a integrar a constante 1. Para ilustrar o processo que leva à formação de uma relação de recorrência, aplico-o ao integral

(mais…)

Março 20, 2010

Relação de recorrência, recursiva ou equação às diferenças associada ao logaritmo de dois (ln 2)

Filed under: Combinatória,Demonstração,Identidade matemática,Matemática,Matemática Discreta,Recorrência,Sucessões,Teorema / Teoria,Teoria dos Números — Américo Tavares @ 4:31 pm
Tags: , , ,

As relações de recorrência associadas a \ln 2 são:

\left( n+1\right) b_{n+1}-3\left( 2n+1\right) b_{n}+nb_{n-1}=0\qquad n\geq 1\qquad \left( 1\right)

e

\left( n+1\right) a_{n+1}-3\left( 2n+1\right) a_{n}+na_{n-1}=0\qquad n\geq 1\qquad \left( 2\right)

em que, a_{0}=1,a_{1}=3 e b_{0}=0,b_{1}=2, podendo demonstrar-se  [1, secção 3] que

\dfrac{b_{n}}{a_{n}}\rightarrow \ln 2\qquad \left( 3\right) .

A fórmula explícita da sucessão \left( a_{n}\right) , — de inteiros — é, como demonstraremos, dada por:

a_{n}=\displaystyle\sum_{k=0}^{n}\dbinom{n}{k}\dbinom{n+k}{k}\qquad \left( 4\right)

pelo que

a_{n+1}=\dbinom{2n+2}{n+1}+\displaystyle\sum_{k=0}^{n}\dbinom{n+1}{k}\dbinom{n+1+k}{k}

e

a_{n-1}=\displaystyle\sum_{k=0}^{n}\dbinom{n-1}{k}\dbinom{n-1+k}{k}

Vamos mostrar que \left( 4\right) verifica \left( 2\right) .

Escrevendo

B_{n,k}=-\left( 4n+2\right) \dbinom{n}{k}\dbinom{n+k}{k}

será

B_{n,k-1}=-\left( 4n+2\right) \dbinom{n}{k-1}\dbinom{n+k-1}{k-1}

Assim

B_{n,k}-B_{n,k-1}=

 

=-\left( 4n+2\right) \dbinom{n}{k}\dbinom{n+k}{k}+\left( 4n+2\right) \dbinom{n}{k-1}\dbinom{n+k-1}{k-1}

 

Substituindo agora a_{n+1},a_{n} e a_{n-1} na relação de recorrência, vem

\left( n+1\right) \left[ \dbinom{2n+2}{n+1}+\displaystyle\sum_{k=0}^{n}\dbinom{n+1}{k}\dbinom{n+1+k}{k}\right]

 

-3\left( 2n+1\right) \displaystyle\sum_{k=0}^{n}\dbinom{n}{k}\dbinom{n+k}{k}+n\displaystyle\sum_{k=0}^{n}\dbinom{n-1}{k}\dbinom{n-1+k}{k}=0

donde

-\left( n+1\right) \dbinom{2n+2}{n+1}=

 

=\displaystyle\sum_{k=0}^{n}\left[ \left( n+1\right) \dbinom{n+1}{k}\dbinom{n+1+k}{k}-3\left( 2n+1\right) \dbinom{n}{k}\dbinom{n+k}{k}\right] +\displaystyle\sum_{k=0}^{n}\left[n\dbinom{n-1}{k}\dbinom{n-1+k}{k}\right]

 

=\displaystyle\sum_{k=0}^{n}\left[ -\left( 4n+2\right) \dbinom{n}{k}\dbinom{n+k}{k}+\left( 4n+2\right) \dbinom{n}{k-1}\dbinom{n+k-1}{k-1}\right]

 

=\displaystyle\sum_{k=0}^{n}B_{n,k}-B_{n,k-1}

que é uma soma telescópica em k. Prosseguindo, tem-se

-\left( n+1\right) \dbinom{2n+2}{n+1}=B_{n,n}-B_{n,-1}=B_{n,n}

porque B_{n,-1}=0. Mas

B_{n,n}=-\left( 4n+2\right) \dbinom{2n}{n}

pelo que basta verificar que

\left( n+1\right) \dbinom{2n+2}{n+1}=\left( 4n+2\right) \dbinom{2n}{n}

é  uma identidade, o que deixo ao cuidado dos meus leitores.

__________

[1] Eric Reyssat, Irrationalité de \zeta (3) selon Apéry, Séminaire Delange-Pisot-Poitou (Théorie des nombres) 20e année, 1978/79, nº 6, 6 p.

P.S: retirei uma igualdade desnecessária para esta demonstração e acrescentei [1].

Março 9, 2010

Razão entre dois termos sucessivos da sucessão (ou sequência) de Fibonacci; relação com os mercados financeiros

Filed under: Demonstração,Fibonacci,Matemática,Recorrência,Sucessões — Américo Tavares @ 9:37 pm
Tags: , , ,

No artigo de Arsélio Martins,  Média e extrema razão e número de ouro – comentário à margem, de 2.03.10, do GEOMETRIA, cita-se uma passagem de um «texto de um boletim de um banco português», dos analistas de acções Ramiro Loureiro e Sónia Martins, que transcrevo em parte:

« ‘Na sequência de Fibonacci (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …), em que um algarismo é dado pela soma dos dois anteriores, a partir de determinada ordem o rácio de um número dividido pelo seu sucessor é de 61,8%. Este nível, juntamente com o 38,2% (100%-61,8%=38,2%), e o 50%, são chamados de níveis de correcção de Fibonacci. O de 61,8% é tido em conta nas correcções fortes de mercado, enquanto o de 38,2% para correcções mais fracas. Consequentemente, o rácio da divisão de um número na sequência de Fibonacci pelo seu antecessor é  161,8%, logo os níveis 138,2%, 150% e 161,8% são os mais usados em tendências positivas para as projecções de price target de Fibonacci (…).’ »

Citando a parte «a partir de determinada ordem o rácio de um número dividido pelo seu sucessor é de  61,8%», para dar uma explicação possível, escrevi, em comentário:

« A sucessão de Fibonacci é gerada pela seguinte relação de recorrência x_{n+1}=x_{n}+x_{n-1} com as condições iniciais x_{1}=x_{2}=1.  Assim

\dfrac{x_{n+1}}{x_{n}}=1+\dfrac{x_{n-1}}{x_{n}}

\lim \dfrac{x_{n+1}}{x_{n}}=1+\lim \dfrac{x_{n-1}}{x_{n}}=1+\dfrac{1}{\lim \dfrac{x_{n}}{x_{n-1}}}

Se esta sucessão tiver limite, há-de ser maior do que um (por a sucessão de Fibonacci ser crescente) e satisfazer a relação

l=1+l^{-1}

em que

l=\lim \dfrac{x_{n+1}}{x_{n}}=\lim \dfrac{x_{n}}{x_{n-1}}>1

Por isso

l^{2}=l+1

l^{2}-l+1=0

ou

l=\dfrac{1+\sqrt{5}}{2}=\Phi

e o limite de aproximadamente 61,8\% é o inverso de l :

\dfrac{2}{1+\sqrt{5}}\approx 0,61803. »

Poderá ver a dedução da fórmula explícita do termo geral da sucessão de Fibonacci nesta minha entrada já antiga.

Fevereiro 25, 2010

Alguns dos fractais mostrados no Fraktale Welten gerados por fórmulas de iteração que sugeri ao autor

Filed under: Fractais,Matemática,Recorrência,Sucessões — Américo Tavares @ 10:01 am
Tags: , ,
Partindo da fórmula de iteração conhecidíssima que cria o conjunto de Mandelbrot

z_{n+1}=z_n^2+c,

[ em que c=z_0=x_0+iy_0=\text{Re}(c)+i\text{Im}(c) é uma constante complexa, correspondente ao início da trajectória de iteração assim gerada no plano complexo ], em Doppelpot , do blogue alemão  Fraktale Welten, de Nachtwaechter, explica-se que, quando, numa fórmula de iteração ou de recorrência, se utilizam duas potências complexas diferentes, os fractais obtidos podem ser especialmente belos; e, ao ler, na continuação: 

»So sinnlos eine derartige Formel mathematisch ist, so hübsch sind die damit erzeugten Bilder, insbesondere die Bilder der Julia-Mengen«

«Uma fórmula desse tipo é tão desprovida de sentido matemático quanto  belas são as imagens que produz, especialmente as dos conjuntos Julia»,  

lembrei-me de sugerir ao autor que experimentasse usar as seguintes fórmulas de iteração:

  1. z_{n+2}=z_{n+1}^{2}+z_{n}+c
  2. z_{n+1}=z_{n}^{z_{n}c}
  3. z_{n+1}=z_{n}^{z_{n}+c}
  4. z_{n+2}=z_{n+1}^{3}+c^{z_{n}}
  5. z_{n+1}=z_{n}^{c}, etc.

No seu artigo Fünf Formeln (cinco fórmulas) explica e mostra os fractais assim gerados: o básico (Grundform), um pormenor (Detail), e o conjunto do tipo Julia (Julia-artige Menge).

A primeira destas fórmulas  ,  que é semelhte à de Mandelbrot, gera, talvez por isso,  um fractal parecido ao de Mandelbrot.  Mostro-os de seguida, pela ordem em que aparecem no artigo, e que são, respectivamente: o global, um pormenor e o do conjunto do tipo Julia.

z_{n+2}=z_{n+1}^{2}+z_{n}+c   

(A)

(B) 

(C)

Os fractais da fórmula de recorrência 4 são estes, respectivamente,  o global, um pormenor e o do conjunto do tipo Julia:

z_{n+2}=z_{n+1}^{3}+c^{z_{n}}

(D)

(E)

(F)

 

No artigo referenciado representam-se os restantes, bem com explicações e opiniões do autor, e ainda os códigos usados em Ultra Fractal 5 para  gerar os fractais. 

Agora uma sondagem:

(A) vista global do fractal gerado por z_{n+2}=z_{n+1}^{2}+z_{n}+c

(B) pormenor de (A)

(C) conjunto tipo Julia de (A)

(D) vista global do fractal gerado por z_{n+2}=z_{n+1}^{3}+c^{z_{n}}

(E) pormenor de (D)

(F)  conjunto tipo Julia de (D)

Edição de 25.02.10: incluída sondagem e aperfeiçoado o texto.

Fevereiro 16, 2010

Descobrir a relação de recorrência de uma sucessão (sequência) e somas estranhas

Filed under: Matemática,Problemas,Recorrência,Sucessões — Américo Tavares @ 1:14 pm
Tags: , ,

Neste desafio do Matemativerso pergunta-se qual é o termo seguinte da sucessão

1, 2, 6, 42, 1806,\dots .

A minha resposta, a aguardar moderação e editada aqui em \LaTeX, foi:

« 3263442

porque cada termo da sequência (sucessão) é igual ao produto de dois factores: o termo anterior e a sua soma com um.

2 = 1\times 2

6 = 2\times 3

42 = 6\times 7

1806 = 42\times 43

3263442 = 1806\times 1807

O sétimo será:

3263442\times 3263443 = 10650056950806 »

A relação de recorrência desta sucessão, cuja  condição inicial é x_1=1, pode ser dada pela expressão  

x_n=x_{n-1}(x_{n-1}+1).

Haverá sucessões diferentes desta, mas cujos primeiros termos sejam os apresentados ?

* * *

ADENDA de 20.02.10: alterei o título e acrescento agora um outro desafio colocado, em 17.02.10, pela autora do Matemativerso.

    « Se

 

    2+3=10
    7+2=63
    6+5=66
    8+4=96

    Então

     9+7= ??? »

A minha resposta foi:

« Solução proposta: 144 »

complementada posteriormente por

« Não enviei a minha justificação para o 144. Ei-la:

(2+3)2=10

(7+2)7=63

(6+5)6=66

(8+4)8=96

(9+7)9=144»

É óbvio qual o critério que segui para chegar ao 144: a soma do lado esquerdo da “igualdade” vai ser multiplicada pelo primeiro termo dessa soma, transformando-se então numa verdadeira igualdade. No entanto,  repito o espírito da dúvida colocada acima. Neste caso poderá haver outros padrões que se descubram e que conduzam a resultados diferentes, parece-me a mim.

Junho 4, 2009

Definições equivalentes dos polinómios de Chebyshev ( ou Tchebycheff )

Filed under: Exercícios Matemáticos,Matemática,Métodos Numéricos,Recorrência — Américo Tavares @ 2:19 pm
Tags: ,

Mostre que as duas definições A e B dos polinómios de Chebyshev ou Tchebycheff  (dependendo da transliteração adoptada) são equivalentes.

A – O polinómio de Chebyshev T_n(x) de ordem n\ge 0  verifica a relação de recorrência

T_0(x)=1, T_1(x)=x,

T_{n+1}=2xT_n(x)-T_{n-1}(x) para n>0.

B – Para todo o inteiro n\ge 0 o polinómio de Chebyshev  é dado por

T_n(x)=\cos (n\arccos x).

Outubro 16, 2008

Limite da raiz de índice n do termo geral de uma sucessão

Filed under: Análise Matemática,Caderno,Cálculo,Demonstração,Exercícios Matemáticos,Matemática,Matemáticas Gerais,Problemas,Recorrência,Sucessões,Teorema / Teoria — Américo Tavares @ 9:20 am
Tags: , , , , , ,

pdf: ver caderno

Se o termo geral de uma sucessão for constante (u_{n}=c), a sucessão tende para para essa constante, como muito bem se sabe. Neste caso a razão \dfrac{u_{n+1}}{u_{n}}=\dfrac{c}{c}=1. E qual é o limite de \sqrt[n]{u_{n}}=\sqrt[n]{c} quando c>0? É bem conhecido (por exemplo ([1,2]) que é também 1:

\lim \dfrac{u_{n+1}}{u_{n}}=\dfrac{c}{c}=\lim \sqrt[n]{u_{n}}=\lim \sqrt[n]{c}=1.

Considere agora o leitor que u_{n}=c^{n}, com c>0. Como \sqrt[n]{c^{n}}=c claro que \lim \sqrt[n]{u_{n}}=c. Por outro lado, sendo neste caso \lim \dfrac{u_{n+1}}{u_{n}}=\dfrac{c^{n+1}}{c^{n}}=c, verifica-se igualmente a igualdade

\lim \dfrac{u_{n+1}}{u_{n}}=\lim \sqrt[n]{u_{n}}. leia o resto »

Julho 27, 2008

Uma nova relação de recorrência geradora de números primos e 1′s demonstrada por Eric Rowland

Filed under: Computação,Matemática,Notícia,Recorrência,Software,Sucessões,Teoria dos Números — Américo Tavares @ 9:10 am
Tags: , , , ,
Eric Rowland demonstrou que a seguinte relação de recorrência só gera 1′s e números primos 

a(n)-a(n-1)=\text{mdc }(n,a(n-1))

(com a condição inicial a(1)=7) no artigo recentemente publicado no Journal of Integer Sequences, Vol. 11 (2008), Article 08.2.8  intitulado  A Natural Prime-Generating Recurrence cujo resumo transcrevo:

« For the sequence defined by a(n) = a(n-1) + gcd(n,a(n-1)) with a(1) = 7 we prove that a(n)-a(n-1) takes on only 1’s and primes, making this recurrence a rare naturally occurring generator of primes. Toward a generalization of this result to an arbitrary initial condition, we also study the limiting behavior of a(n)/n and a transience property of the evolution. »

\bigskip

["gcd" significa "greatest common divisor"]

\bigskip

Anteriormente tive oportunidade de ler alguns artigos de Rowland sobre a função zeta de Riemann publicados há uns anos na Internet. 

\bigskip

Actualização de 2-8-2008: Eric Rowland indica neste post A simple recurrence that produces complex behavior — and primes! de A New Kind of Science Blog a origem deste seu trabalho. Entretanto criou esta demonstração que explora a recorrência. Inicialmente tomei conhecimento deste artigo de Eric Rowland, no JIS, neste post de Jeffrey Shallit no blogue Recursivity , através desta entrada do blogue Logic Nest.

\bigskip

Seja r(n)=a(n)-a(n-1). O seguinte código permite obter, no software PARI (free software com licença GNU General Public License), os termos diferentes de um, para 2<n<101, da sucessão r(n).

r(5)=5,r(6)=3,r(11)=11,r(12)=3,r(23)=23, r(24)=3,r(47)=47,r(48)=3,r(50)=5,r(51)=3.

Todos os outros são iguais a um.

N=2;
X=7;
while(N<101,
  Y= X+gcd(N,X);
  if (Y-X>1,
    print(N ” : ” Y-X)
  );
  X=Y;
  N=N+1
)

 

Junho 15, 2008

Iterações fractais

Filed under: Fractais,Matemática,Recorrência — Américo Tavares @ 9:21 am
Tags: ,

Nesta entrada  Klaus Mustermann escreve no seu blogue Fraktale Welten  sobre a iteração de Manowar, que origina o fractal de Manowar, através da relação de recorrência

z_{n+1}=z_{n}^{2}+z_{n-1}+z_0.

Teve a ideia de generalizar esta relação, usando a recorrência

z_{n+1} = f_{1}(z_n) + f_{2}(z_{n-1})+z_0,

em que f_1,f_2 são funções arbitrárias, que produzem fractais diferantes conforme a sua escolha.

Eis uma imagem das que é possível gerar escolhida entre as que lá são apresentadas, da qual gosto particularmente:

  

E007 064

 

Página Seguinte »

Tema: Rubric. Blog em WordPress.com.