Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
All these numbers are multiples of $1/2$, which means that the floor changes as... ? –  juanrapha Jun 24 at 11:08

1 Answer 1

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|improve this answer
    
nice solution by using leaping induction! –  user132603 Jun 25 at 14:18

Your Answer

 
discard

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.