1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – user142522
    Commented Apr 13, 2014 at 17:10
  • $\begingroup$ 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. $\endgroup$
    – shadow10
    Commented Apr 13, 2014 at 17:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .