Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

let $n$ be a positive integer, prove that $$\sum_{i=0}^{\left\lfloor\frac{n}{3}\right\rfloor}\left\lfloor\frac{n-3i}{2}\right\rfloor=\left\lfloor\frac{n^2+2n+4}{12}\right\rfloor.$$ It looks like we have to consider lots of cases to solve the problem. Are there any simple solutions?

share|cite|improve this question
All these numbers are multiples of $1/2$, which means that the floor changes as... ? – guaraqe Jun 24 '14 at 11:08

I think this is an easy way to handle it. We induct on $n$. See we use a step argument. Call $$S_n=\sum_{i=0}^{\lfloor{n/3}\rfloor}\left\lfloor{\frac{n-3i}{2}}\right\rfloor$$ We have to prove $S_n=\left\lfloor{\dfrac{(n+1)^2+3}{12}}\right\rfloor \tag{1}$ Now $S_{n+3}-S_{n}=\left\lfloor{\dfrac{n+3}{2}}\right\rfloor$ To prove $(1)$ we need to prove: $$ \left\lfloor{\dfrac{(n+1)^2+3}{12}}\right\rfloor+\left\lfloor{\dfrac{n+3}{2}}\right\rfloor=\left\lfloor{\dfrac{(n+4)^2+3}{12}}\right\rfloor\tag{2}$$ To prove $(2)$ we replace $n$ by $n-1$ and $$\left\lfloor{\dfrac{n^2+3}{12}}\right\rfloor+\left\lfloor{\dfrac{n+2}{2}}\right\rfloor-\left\lfloor{\dfrac{(n+3)^2+3}{12}}\right\rfloor=Q_n$$ Now we show $$Q_{n+6}=Q_n\tag{3}$$ which is a consequence of trivial algebra. Hence to prove $(2)$ for all $n$ we only need prove it for $n=0,1,2,3,4,5$ due to $(3)$. Which is trivial. Now to prove $(1)$ for all $n$ we need to check $n=0,1,2$ and we are again done. Note I haven't done all the calculations, they are left for the OP, but I have checked they are true indeed. I suppose this answers your questions.

share|cite|improve this answer
nice solution by using leaping induction! – user132603 Jun 25 '14 at 14:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.