In how many ways can three distinct numbers be chosen from the set $\{1,2,3,4,\dots,2n\}$ such that the numbers are in increasing arithmetic progression?
Progress: The common difference for the selected numbers can lie between 1 to $2n/3$. So it seems I need to work for every common difference from $1$ to $2n/3$. Is this fine?
On
This is an extended hint.
If you add $2n+1$ to the set, you get some extra APs, but note that the extra APs you get all include $2n+1$ - for example $[2n-1, 2n, 2n+1]$ is added, with difference $1$ and $[2n-3, 2n-1, 2n+1]$ with difference $2$. $[1, n+1, 2n+1]$ also gets added, with difference $n$.
You can count these, and also the ones you get when you additionally add $2n+2$ to the set.
Also check with small values what gets added to ensure your calculations are right. With a bit of testing you should see what is happening.
On
Solution: The second term of the AP is determined entirely by the other two terms.But the first term $a$ and third term $a+2d$ have the same parity(adding the even number $2d$ does not change their parity).
If they are both odd,then they can be selected in $\dbinom{n}{2}$ ways.
If they are both even,they can be selected in $\dbinom{n}{2}$ ways.
Adding them up,we get $n(n-1)$.
Credits: Thanks to Mark Bennet for helping me with this solution.
The number of progressions $\{a_1,a_2,a_3\}$ such that $a_2=k$ is:
so the total number is $$S=\sum_{k=2}^n (k-1)+\sum_{k=n+1}^{2n-1} (2n-k)$$
The first sum is $1+2+\ldots+(n-1)=\frac{n^2-n}2$, and the second sum is the same, but in the reverse order. This gives $$S=n^2-n$$
Another solution:
We can count how many AP's with difference $d$ there are. If the first term is $1$, the last is $1+2d$, so there are $2n-(1+2d)+1=2n-2d$ of such AP's. But $d$ can be any integer from $1$ to $n-1$, so $$S=\sum_{d=1}^{n-1}(2n-2d)=\sum_{k=1}^{n-1} 2k=n^2-n$$