# $\sum _{k=1}^{2n} T(k) = \sum _{k=1}^{2n} k$

For the Collatz function $$T(n)=\frac {3n+1}{2} \text {if} \ n \ \text{is odd}$$ and $$T(n)=\frac {n}{2} \text {if} \ n \ \text{is even }$$ I have found that $$\sum _{k=1}^{2n} T(k) = \sum _{k=1}^{2n} k$$

Proof:$$\sum _{k=1}^{2n} T(k) = \{T(1)+T(3)+T(5)+...+T(2n-1)\} + \{T(2) +T(4) +...+T(2n)\}$$

$$= \frac {3(1)+1}{2} +\frac {3(3)+1}{2}+...+\frac {3(2n-1)+1}{2} +1+2+3+...+n$$

$$= \frac {3n^2 +n}{2} + \frac {n(n+1)}{2} = n(2n+1)=\sum _{k=1}^{2n} k.$$

Question: Are there other non-trivial sets $S$ which satisfy $$\sum _{k\in S}T(k) = \sum _{k\in S} k$$

• This is a simple extension of your proof, but by linearity of sums since you have shown that $T(k)-k$ sums to zero on $S=[1,...,2n]$ for all $n$, we can take differences (or just calculate easily) to see that the same is true for $\{2n-1,2n\}$ and sum up to see that whenever $S$ is a finite set of adjacent odd-even pairs like $\{1,2,5,6,17,18\}$ then this property holds. So maybe a better question is whether there are any sets $S$ which are not of this form. – Mario Carneiro Jul 11 '18 at 0:56
• This $n-(-1)^n$ maybe? – Natural Number Guy Jul 11 '18 at 1:44

For $S\subseteq\mathbb N$, let the even-odd decomposition of $S$ be the unique sets $A,B$ such that $S=\{2n-1\mid n\in A\}\cup \{2n\mid n\in B\}$.
Theorem: A set $S$ satisfies $\sum_{n\in S}T(n)=\sum_{n\in S}n$ if and only the sets $A,B$ in the even odd decomposition of $S$ have equal sum.
This immediately produces many examples, just by picking sets with the same sum like $A=\{1,2,6\}$ and $B=\{2,3,4\}$ and combining them into $S=\{1,3,4,6,8,11\}$.
Proof: \begin{align} \sum_{n\in S}(T(n)-n)&=\sum_{n\in A}(T(2n-1)-(2n-1))+\sum_{n\in B}(T(2n)-2n)\\ &=\sum_{n\in A}\left[\frac{3(2n-1)+1}{2}-(2n-1)\right]+\sum_{n\in B}(n-2n)\\ &=\sum_{n\in A}n-\sum_{n\in B}n \end{align} Therefore $\sum_{n\in S}(T(n)-n)=0$ if and only if $\sum_{n\in A}n=\sum_{n\in B}n$.