ELEMENTOS: 071-Função A(m,k)

Seja a sucessão numérica

, com $[;m \geq 3;]$

Defino a função [;A(m,k);]

como o número de subsequências de [;k;]

termos ( com $[;3 \leq k \leq m;]$ ) contidas em [;A;]

, que estejam em progressão aritmética [;(PA);]

, com razão inteira [;r>0;]

Por exemplo, com [;m=5;]

, temos

e as

crescentes de [;k=3;]

termos contidas em [;A;]

são

Logo,

Neste caso temos apenas três valores para [;A(m,k);]

, tendo em vista que $[;3 \leq k \leq 5;]$ . Verifiquem que os outros dois valores são [;A(5,4)=2;]

A fórmula para [;A(m,k);]

$[;A(m,k)=\sum_{r=1}^{\left[\frac{m-1}{k-1}\right]}m-(k-1)r;]$

onde $[;\left[\frac{m-1}{k-1}\right];]$ é a parte inteira de $[;\frac{m-1}{k-1};]$

Demonstração

A razão

está contida em um intervalo condicionado ao número [;k;]

de termos e a quantidade [;m;]

de números da sequência [;A;]

, pois o último termo da progressão aritmética de primeiro termo [;a_1=1;]

tem que ser $[;a_k=1+(k-1)r \leq m \Rightarrow r \leq \left[\frac{m-1}{k-1}\right];]$ .

Existe uma progressão aritmética de último termo [;a_k=m;]

, cujos termos antecessores são

$[;a_{k-1}=m-r;]$

$[;a_{k-2}=m-2r;]$

Onde

é o maior dos primeiros termos de todas as [;PAs;]

de razão

contidas em [;A(1,2,...,m);]

, ou seja

$[;1 \leq a_1 \leq a_1(max);]$

Consequentemente, o número de [;PAs;]

termos e de razão [;r;]

contidos em [;A;]

é exatamente:

No entanto, com o mesmo número de termos [;k;]

, a sucessão [;A(1,2,...,m);]

pode suportar outras [;PAs;]

de razões diferentes e como vimos, estas razões variam no intervalo $[;1 \leq r \leq \left[\frac{m-1}{k-1}\right];]$ . Logo,

$[;A(m,k)=\sum_{r=1}^{\left[\frac{m-1}{k-1}\right]}m-(k-1)r;]$

Exemplos

Sejam

. Queremos saber o número de [;PAs;]

termos contidos na sucessão [;A(1,2,3,4,5,6,7);]

.

Temos que o número de [;PAs;]

contidas em [;A;]

para uma determinada razão [;r;]

Mas como as razões variam no intervalo $[;1 \leq r \leq \left[\frac{m-1}{k-1}\right];]$ ou seja, $[;1 \leq r \leq \left[\frac{7-1}{4-1}\right] \Rightarrow 1 \leq r \leq \left[\frac{6}{3}\right] \Rightarrow 1\leq r \leq 2;]$ , temos que

Para [;r=1;]