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

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.

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

should be correct?

• Hint. Just start counting the number of $1$'s and $2$'s in each case. – Shervin Sorouri Aug 30 '19 at 13:40
• Thanks. Trying to work out a solution. – weno Aug 30 '19 at 13:47

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$$
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}.$$