Fall 2018, problem 72
Comments
Nice simple solution, Luciano! I'm trying to see if an arithmetic series version holds up as well....stay tuned.
r=3 is valid for any even a1 and if a1 is odd then r+1 can be any prime factor of a1.The case (2) only applies to a1 prime.
User 789 has shown that any increasing sequence of length k can be completed by an extra term so that the resulting sequence of length k+1 complies with the divisibility condition. Of course, generally any subsequence of that sequence does not comply with the divisibility condition unlike the sequence defined by lucianosantos.It would be interesting to see whether the geometric sequence is the only one which complies with the divisibility condition for any k.I have tried to do so by looking for a recursive relation for S1 and S2 as a function of k and hence define a recursive relation for the elements of the sequence but to no avail.Can anyone provide an answer ?
Thanks, I see I've misread the question, and didn't realize I needed all k to satisfy the condition for a single sequence. However, by applying the process of attaching a number lots of times to the sequence $a_1 = 2$ , I got the sequence $2, 6, 96, 19968, ...$ where $a_{n+1}= ( \sum_{i=1}^{n} a_i )^2 + \sum_{i=1}^{n} (a_i^2 - a_i) $. I don't see a non recursive way to define this, and I don't know if this was the recursive relation you're talking about, but it should satisfy the divisibility condition.
Well the two methods give two different sequences,one is the geometric one and the other a much faster growing sequence.It is even possible to build a sequence which is geometric up to n and continue the sequence with the other method.This mixed sequence will satisfy fully the divisibility condition for all k so we can safely say that there are an infinity of such sequences which satisfy the problem'
In fact, for any increasing sequence $a_1, a_2, ... ,a_k$ of positive integers other than a single 1, an integer $n>a_k$ can be added at the end to make $a_1^2+a_2^2+...+a_k^2+n^2$ divisible by $a_1+a_2+...+a_k+n$. The solution of this problem follows from there.
Let's return to the sequence $a_1, a_2, ... a_k$. I'll define $S_1 := a_1+...+a_k$ and $S_2 := a_1^2+...+a_k^2+S_1^2$ to use as a shorthand.
Now, the number we want to add is $S_2-S_1$. The sequence now becomes $a_1, a_2, ... a_k, S_2-S_1$ , where the sum of the numbers is $S_2$ and the sum of the squares is equal to $S_2^2-2S_1S_2+S_2$ , which is clearly divided by $S_2$. This might be easier to see by calculating the sum of the squares modulo $S_2$.
All that's left is to prove that $S_2-S_1$ is actually larger than $a_k$. When the initial sequence is a single integer $t$, $S_2-S_1 = 2t^2-t$ , which is larger than t for all $t>1$. Afterwards, adding any integer $m\<t$>
Edit: Similar arguments can be applied to higher powers too, so this problem can be solved for any integer power.
The nice result of user789 can be seen as a special case of the following claim, whith the choice $u=\sum_{i=1}^ka_i\,;\ v=\sum_{i=1}^ka_j^2$:
Claim1 Let $u,v$ be given with $1$ < $u$ < $v$. Setting $x:=v+u^2-u$, the sum $u+x$ divides the sum $v+x^2$
In our problem we have a further property, say $u$ divides $v$; but such a property is not needed for the claim. nor is needed in the second claim:
Claim2 If $u$ and $v$ have the same parity, the sum $u+x$ divides the sum $v+x^2$ also with the choice $x:={{v+u^2}\over2}-u$ $\left(^*\right)$
In our problem $u$ and $v$ have the same parity, thus the argument apply to our problem for any $k\ge1$, but for $a_1=2$, where it applies only for $k\ge2$.
Of course this can be combined with the remark of Michel: at any stage we can switch between the fast increase and the slow one.
$-----------------------$
$\left(^*\right)$ if $u$ and $v$ have the same parity, $v+u^2$ is even.
Hi! Used claim 1 to solve the problem
The two methods listed above to create the right sequence were produced by intuition but are there any other methods which could produce a right sequence distinct from those two ? The answer is yes . Indeed I wish to continue the geometric sequence 2,6,18 by a fourth term we call x. From the two methods we get three possible values : 54 (geometric ), 494 (Claudio) and 1014 (User 789). I have searched the solutions of the equation in N:
364+x^2 =p(26+x) where x is the fourth element in the sequence and p is some integer which is the ratio of v/u (with claudio's notation). To solve this equation we must express the fact that the discriminant of the second degree equation is a perfect square and that p must be an integer.The method is a bit tedious but yields the following values for x larger than 18:
x= 26,39,54,78,104,182,233,494,1014.
So there are 9 possible values for x which fit the divisibility requirement and not only 3 ! Unfortunately I cannot propose here other methods but they do exist....
Hi, Michel.
I believe that my method is quite general. In fact, the determinant can be written in the form $$\Delta=(\rho-2a)^2-4(v+a^2)$$ where $\rho$ is future ratio $\frac vu$. In order to have a square as value for $\Delta$ we need a decomposition of the product $4(v+a^2)$ ax $p*q$ with $p,q$ both odd or both even. Both odd is excluded, thus we are left with:
(i) $p=2, q=2(v+u^2)$, solution of User789;
(ii) $p=4, q=v+u^2$; my solution, with $q$ even because of $v+u$ even.
Other solutions, as the ones you get starting from $a_1=2$, can arise only in special cases, say when $v+u^2$ is multiple of $2^n$ with $n>1$.
Hi again Claudio !
This is definitly a very interesting problem.. First in your discriminant you probobly meant that a is u (as defined in your previous post ) and there should be a + sign in the first square of the discriminant. Now my comment is this: your formula is general in the sense that it alwyas works whatever the value of the first element of the sequence but you do miss an awful lot of other possible solutions that you call "special" cases and particularly the geometric solutions. This is due to the fact that v+u^2 is always even (as you mentioned in your first post) but can be generally decomposed in powers of primes which gives more possible values for p(and this even if v+u^2 is twice an odd number). To illustrate this I wish to continue the sequence 3,6. . In that case v+u^2 is equal to 126=2x3x3x7;Using the 3 and 7 for p,q we can generate ,in addition to 117 and 54 as predicted by your formula, the numbers 12 (geometric) and 9. This last value of 9 intrigued me;could it be that the sequence 3,6,9,12,15..... is a right sequence ? Indeed it is ! and strangely this question was raised by TME earlier on. But does it work for all initial values ? Suppose we define the sequence ak= kxa1 Then u=a1x(n)(n+1)/2 and v= a1^2 x n(n+1)(2n+1)/6 (Faulhaber formula of problem 73!) Clearly u divides v if a1 is a multiple of 3 ! So there is a class of arithmetic sequences which fit the requirements. I have the feeling that more general sequences can be found which depend on the initial value.
First of all, 3 remarks:
1) Very nice your result on arithmetic series
2) Thanks for signalling my bad notations: in the formula for $\Delta$ the "$a$" should be a "$u$"
3) I believe that my idea (use the formula for the second degree equation and look at the discriminant) is very stupid! See here down.
Let us put the problem as follows (for the moment we disregard the restriction "$x$ sufficiently big"):
Problem We are given $v>u>0$ with $u+v$ even; we want to find the values of $x$ such that $v+x^2$ is a multiple of $u+x$.
Claim $x$ satisfies if and only if $x+u$ divides $v+u^2$
Proof $x^2+v=[x^2-u^2]+[v+u^2]$ and the first term is obviously a multiple of $x+u$.
Thus no need of discriminant for a second degree equation: we simply look at the (big) factors $F$ of $v+u^2$ and we choose $x=F-u$.
The solution of user789is $F=v+u^2$; my first attempt corresponds to $F={{v+u^2}\over2}$; geometric as well as arithmetic series are very nice miracles, but I do not see other possible miracles...
Consider $(a_{n})$ a geometric sequence, with ratio $r\in \mathbb{N}-\{1\}$.
$ (a_{n}^2) $ is also a g.s. with ratio $r^2$.
Let $S_{n}= a_{1} \frac{1-r^{n}}{1-r} $ and $S'_{n}=a_1^2 \frac{1-(r^2)^{n}}{1-r^2}$.
Then, $\frac{S'_{n}}{S_{n}}= \frac{a_{1}^2}{a_1} \times \frac{1-(r^2)^{n}}{1-r^2} \times \frac {1-r}{1-r^{n}}=a_1\frac{(1-r^n)(1+r^n)}{(1+r)(1-r^n)}= \frac{a_1}{1+r}\times (1+r^n)$.
(1) If $a_1 =2$ and $r=3$ , $\frac{S'_{n}}{S_{n}}= \frac{2}{4}\times (1+3^n) \in \mathbb{N}$.
(2) If $a_1>2$, put $r=a_1 -1$ , and hence $\frac{S'_{n}}{S_{n}} \in \mathbb{N}$.