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

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

How to prove this?

Given a natural number $n$, we determine $f(n)$ by the following algorithm:

1. Set $s=0.$
2. For $i=1,...,n,$

   if $s\geq i,$ set $s=s-i,$

   otherwise, set $s=s+i.$

3. The result $f(n)=s.$

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 $f(12)$ we compute:

$0+1=1$; $1+2=3$; $3-3=0$; $0+4=4$; $4+5=9$; $9-6=3$; $3+7=10$; $10-8=2$; $2+9=11$; $11-10=1$; $1+11=12$; $12-12=0.$

The outcome is that $f(12)=0.$ So $12$ is a zero of function $f.$ I am interested in the sequence of zeros. The first few are $0,3,12,39,120,363,1092,3279,9840,$ in general the numbers of the form ${\tfrac {3}{2}}(3^{k}-1).$ 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)

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 ${\tfrac {3}{2}}(3^{k}-1)+1$ and ${\tfrac {3}{2}}(3^{k}-1)+1+{\tfrac {3}{2}}(3^{k}-1)+2=3^{k+1}$, 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)

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+a²), ... , and in general the kth term is b(a^k-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)

Is the laborious part getting to $f'(k+1)=3(f'(k)+1)$ or the proof by induction? fiveby(zero) 23:33, 5 May 2023 (UTC)

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 ${\tfrac {3}{2}}(3^{0}-1)=0$ and ${\tfrac {3}{2}}(3^{k+1}-1)=3({\tfrac {3}{2}}(3^{k}-1)+1)$

fiveby(zero) 02:26, 6 May 2023 (UTC)

The proof appears to proceed in two phases, each of which requires induction. Define the sequence $s$ by $s_{0}=0$ and $s_{z}=s\odot z$ for $z\geq 1,$ where $s\odot z=s-z$ if $s\geq z,$ and $s\odot z=s+z$ otherwise. In the first phase we prove a formula for $s_{z{+}d},$ where $1\leq d\leq 2z{+}3,$ under the assumption that $s_{z}=0.$ This involves case distinctions based on the parity of $d.$ We then observe that $s_{z{+}d}>0$ if $1\leq d<2z{+}3,$ whereas $s_{z{+}d}=0$ if $d=2z{+}3.$ So if $s_{z}=0,$ the next occurrence of a $0$ is $s_{3z{+}3}=0.$ 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 ${\tfrac {3}{2}}(3^{k}{-}1),$ goes smoothly.  --Lambiam 19:32, 6 May 2023 (UTC)

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 $f'(k+1)=3(f'(k)+1)$ instead of ${\tfrac {3}{2}}(3^{k}-1)$ and series lets me go back to the picture of the state machine. fiveby(zero) 21:24, 7 May 2023 (UTC)

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)

If one has transitions ${\text{A}}\to {\text{B}}\to {\text{A}}$, then the state predicates ${\text{A}}$ and ${\text{B}}$ are not properly called "invariants". But it appears one can indeed use the ${\text{A}}$–${\text{B}}$ alternation to build an argument. Considering the state to be a pair $(s,n)$ and defining $t(s,n)=(s\odot n,n{+}1),$ with initial state $(0,1),$ it is helpful to consider transitions $(s,n)\to t^{2}(s,n)$ taking two steps at once. The new rules of the game are that when $1<s<n$ we take two steps, otherwise one step. We can distinguish three state predicates: ${\text{Z}}(s,n)\Leftrightarrow s=0,$ ${\text{A}}(s,n)\Leftrightarrow 0<s<n,$ ${\text{B}}(s,n)\Leftrightarrow 0<n\leq s.$ Possible transitions are ${\text{Z}}\to {\text{A}},$ ${\text{A}}\to {\text{A}},$ and ${\text{A}}\to {\text{Z}}.$ The ${\text{B}}$ states are always skipped. Now consider the auxiliary quantity $a=2s+n.$ It is left invariant by ${\text{A}}\to {\text{A}}$ transitions, while the quantity $s$ decreases, since ${\text{A}}(s,n)\Rightarrow t^{2}(s,n)=(s{-}1,n{+}2).$ The rest is then a cinch.  --Lambiam 19:59, 9 May 2023 (UTC)