Wikipedia:Reference desk/Archives/Mathematics/2023 May 5

Mathematics desk
< May 4 << Apr | May | Jun >> Current desk >
Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.


May 5

edit

How to prove this?

edit

Given a natural number  , we determine   by the following algorithm:

  1. Set  
  2. For  
    if   set  
    otherwise, set  
  3. The result  

In words, we subtract when we can, but we are not allowed to go negative, so if we can't subtract we add. For example, to find   we compute:

 ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  

The outcome is that   So   is a zero of function   I am interested in the sequence of zeros. The first few are   in general the numbers of the form   While it is not very hard to prove this in a somewhat laborious way, I suspect there is some elegant proof, but it escapes me.  --Lambiam 19:23, 5 May 2023 (UTC)[reply]

I'd guess this is what you did but just to check. The sequence of adds and subtracts after each zero is add followed by pairs of add and subtract till the next zero. The values of n for which f is zero are 3, 3+3^2, 3+3^2+3^3 etc.The two adds after each of these are   and  , and this last number is the number of steps from the zero till the next zero. The values then continue in pairs going down and up by one till zero is reached. And the laborious part is just showing this is true. NadVolum (talk) 20:24, 5 May 2023 (UTC)[reply]
It might help to generalize a bit. Start with any given k and assume g(k)=0, and g(i+1)=g(i)-(i+1) if g(i)>i, g(i)+(i+1) else. So if g(10)=0 then g(11)=11, g(12)=23, g(13)=10, and so on. It shouldn't be too hard to prove by induction that g(k+1)=k+1, g(k+3)=k, g(k+5)=k-1, ... g(k+2s+1)=k+1-s, and g(k+2)=2k+3, g(k+4)=2k+4, g(k+2+2s)=2k+3+s for s≤k+1. I'm pretty sure you'd have to do this by induction and it would be a bit messy, but the pattern is fairly simple so the proof should be straightforward. The upshot would be that if g(k)=0 then the next 0 of g is 3k+3. Starting with k=0 this produces 0, 3, 12, 39, ... . But if you start with 10 you get 10, 33, 69, ... . In any case, at this point it amounts to turning the recursion z(i+1)=3*z(i)+3 into an explicit formula. More generally, if z(0)=0, z(i+1)=a*z(i)+b, then the sequence of z's is 0, b, b(1+a), b(1+a+a2), ... , and in general the kth term is b(ak-1)/(a-1). So I don't know about elegant, perhaps generalizing makes it more messy in the long run. If you start with different initial values for g, say g(k)=n, then the behavior of g is more complex; it takes a while to get into the range [0, 2k] and then it starts following the predictable up-down pattern. A complete description including the "transient" would be rather complex. --RDBury (talk) 22:29, 5 May 2023 (UTC)[reply]
Is the laborious part getting to   or the proof by induction? fiveby(zero) 23:33, 5 May 2023 (UTC)[reply]
iff s = 0 you have to add twice, if you've added twice you have to subtract, if you just subtracted you have to add, if you add then subtract you reduce s by one, so ++-+-+-+-...until you get back to 0
if f(i) = 0 then f(i+1) = i+1 and f(i+1 + 2(i+1)) = 0
the induction part is   and  
fiveby(zero) 02:26, 6 May 2023 (UTC)[reply]
The proof appears to proceed in two phases, each of which requires induction. Define the sequence   by   and   for   where   if   and   otherwise. In the first phase we prove a formula for   where   under the assumption that   This involves case distinctions based on the parity of   We then observe that   if   whereas   if   So if   the next occurrence of a   is   If you write this all out neatly, it seems rather a lot for such a simple thing. But the proof is not convincing unless you also verify the low-level stuff. The second phase, proving the formula   goes smoothly.  --Lambiam 19:32, 6 May 2023 (UTC)[reply]
Sorry was definitely thinking along the lines of 'explanatory' and not rigorously convincing, and sorry for linking induction. It's a state machine with accumulator, draw picture, hold up picture is pretty rigorous for me. Thinking   instead of   and series lets me go back to the picture of the state machine. fiveby(zero) 21:24, 7 May 2023 (UTC)[reply]
Lambiam, i'm thinking of this as writing invariants about states, instead of proving a formula with case distinctions based on parity. Of all the states divide into unreachable states, states where invariant A holds and states where invariant B holds, and transitions must be A->B->A (after the first state). I don't know if this is the same amount of work or not, or just a bunch of hand-waving. But what about thinking instead of dividing the series i+2,i+3,i+4... into sets each of which is a series and take the difference of those two sets? Same amount of work? fiveby(zero) 17:58, 9 May 2023 (UTC)[reply]
If one has transitions  , then the state predicates   and   are not properly called "invariants". But it appears one can indeed use the    alternation to build an argument. Considering the state to be a pair   and defining   with initial state   it is helpful to consider transitions   taking two steps at once. The new rules of the game are that when   we take two steps, otherwise one step. We can distinguish three state predicates:       Possible transitions are     and   The   states are always skipped. Now consider the auxiliary quantity   It is left invariant by   transitions, while the quantity   decreases, since   The rest is then a cinch.  --Lambiam 19:59, 9 May 2023 (UTC)[reply]