$\sum_{i=1}^{n} GCD(i + 1, 2)$

Question

I need to calculate the following sum: $$S_{n} = \sum_{i=1}^{n} GCD(i + 1, 2)$$

where $GCD(x,y)$ stands for greatest common divisor of $x$ and $y$.

The terms of this sum simply boil down to:

$$\underbrace{2}_{a_{1}} + \underbrace{1}_{a_{2}} + \underbrace{2}_{a_{3}} + \underbrace{1}_{a_{4}} + \underbrace{2}_{a_{5}} + \underbrace{1}_{a_{6}} + ... $$

What might be worth noting is that the last term is $1$ if $n$ is even, and $2$ if $n$ is odd.

I need to compute the result as a function depending on $n$, that is: $S_{n} = f(n)$.

I was thinking about splitting it into two cases:

$$S_{n} = \begin{cases} f_{1}(n) \quad \iff \text{n is odd} \\ f_{2}(n) \quad \iff \text{n is even}\end{cases}$$

Any ideas on how to proceed with computing the result?

---

I computed the $f_{2}(n)$ and got $f_{2}(n)= \frac{3}{2}n$. Also, I believe $f_{1}(n)= \lceil \frac{3n}{2} \rceil$ would work.

So the final answer as:

$S_{n}= \lceil \frac{3}{2}n \rceil$

should be correct?

Answer 1

If $i$ is even then the $GCD(i+1,2)=1$. If $i$ is odd then $GCD(i+1,2)=2$. The number of even number is $\left \lceil \frac{n}{2} \right \rceil$. The number of odds $n-\left \lfloor \frac{n}{2} \right \rfloor$. The formula is so: $$S_n=1\cdot\left \lfloor \frac{n}{2} \right \rfloor+2\cdot\left(n-\left \lfloor \frac{n}{2} \right \rfloor\right)=2n-\left \lfloor \frac{n}{2} \right \rfloor$$

Answer 2

If $n=2k+1$ (odd) then there will be $k$ even nos. and $k+1$ odd nos. between $1$ and $n$. So the required sum will be $$S(n)=(k+1)1+(k)2=3k+1=\frac{3}{2}(n-1)+1=\frac{3n-1}{2}.$$ Likewise you can get the answer when $n$ is even as $$S(n)=3k=\frac{3n}{2}.$$