# How to find a pattern in this recursive sequence algorithmically?

I'm trying to find the closed-form of a sequence algorithmically.

Here is the recursive sequence: $$w_k=w_{k-2}+k, \forall k \in \Bbb{Z} | k \geq 3, w_1=1, w_2=2$$ which produces this sequence: $1,2,4,6,9,12,16,22,25,30,...$ which has the following explicit formula after a bit of trial and error: $$w_n=\begin{cases} ({\frac{n+1}{2}})^2 \text{if } n \text{ is odd}\\ \frac{n}{2}(\frac{n}{2}+1) \text{if } n \text{ is even}\\ \end{cases}$$ How can I do this without randomly guessing or trial and error?

Well you could do it by telescoping. Since the jump here is $2$ i.e we get $w_k$ from $w_{k-2}$ it is clever to divide it into odd and even cases.Suppose we want to find $\{w_{2k}\}$ Now see that $w_{2k+2}-w_{2k}=2k+2$ sum this for $k=1$ to $k=n-1$ then get $w_{2n}-w_2=n(n-1)+2n-2=n^2+n-2\implies w_{2n}=n^2+n$ precisely the formula for $n=$ even.Similarly we get $w_{2n+1}-w_{2n-1}=2n+1$ and summing over we have $w_{2n+1}=(n+1)^2$.This is the method that will work here.
• Why did you sum it from k=1 to k=n-1? And I don't see how you got $w_{2n}-w_2=n(n-1)+2n-2=n^2+n-2\implies w_{2n}=n^2+n$. Commented Apr 13, 2014 at 17:10
• Ummm summing to $n-1$ means the last term left is $w_{2(n-1)+2}=w_{2n}$ and the equality holds since $w_2=2$ and $n(n-1)+2n-2=n^2+n-2$ I hope this is understandable since there is nothing except plain arithmetic in it.Hope this helps. Commented Apr 13, 2014 at 17:14