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.

An other sequence that arise in context of formula for number of partitions of number natural in parts non greater than 5 is

$81,123,167,229,295,381,473,587, 709, 855,1011,1193,1387,1609,1845,2111,2393,2707,3039,..$

If we try method of finite differences we get following sequences

$ 42 ,44 ,62, 66 ,86 ,92,114, 122,146, 156, 182 , 194, 222,….$

$ 2 , 18, 4 , 20, 6, 22, 8 , 24, 10, 26, 12, 28,,…$

$16 , -14, 16, -14, 16, -14, 16, -14 , 16 , -14, 16,…$

$-30, 30 , -30 , 30, -30, 30, -30, 30, -30 , 30,…$

Method of finite differences is useless. How to find general term.

share|improve this question
7  
It looks as if differences are very useful here. –  André Nicolas Aug 7 '11 at 15:00
1  
Method of finite differences is useless? Oh come on. You clearly have shown that they are useful! The fourth-forward difference is 30(-1)^n. Can't you guess the sequence with that in hand? –  Patrick Da Silva Aug 7 '11 at 16:58

2 Answers 2

up vote 7 down vote accepted

Alternatively, when you see the alternating signs, split it into two interlocking subsequences, $81,167,295,473,709,1011,\dots$ and $123,229,381,587,855,1193,\dots$. The first subsequence has first differences $86,128,178,236,302,\dots$, second differences $42,50,58,66,\dots$, and third differences $8,8,8,\dots$, and the second subsequence has first differences $106,152,206,268,338,\dots$, second differences $46,54,62,70,\dots$, and third differences $8,8,8,\dots$. Work with these separately.

If the first subsequence is $x_0,x_1,\dots$, its first differences are $\Delta x_0,\Delta x_1,\dots$, and its second differences are $\Delta^{(2)} x_0,\Delta^{(2)} x_1,\dots$. The third differences are apparently constant at $8$, so it should be clear that $\Delta^{(2)} x_n = 42 + 8n$. This means that $$\begin{align*} \Delta x_n &= 86 + \sum\limits_{k=0}^{n-1} (42 + 8k)\\ &= 86 + 42n + 8\sum\limits_{k=0}^{n-1}k\\ &= 86 + 42n + 8 \left(\frac{n(n-1)}{2}\right)\\ &= 86 + 42n + 4n(n-1)\\ &= 86 + 38n + 4n^2. \end{align*}$$ Repeat the process one more time: $$\begin{align*} x_n &= 81 + \sum\limits_{k=0}^{n-1}(86 + 38k + 4k^2)\\ &= 81 + 86n + 38\sum\limits_{k=0}^{n-1}k + 4\sum\limits_{k=0}^{n-1}k^2\\ &= 81 + 86n + 19n(n-1) + 4\left(\frac{(n-1)n(2n-1)}{6}\right)\\ &= 81 + 67n + 19n^2 + \frac{2}{3}n(2n^2-3n+1)\\ &= 81 + \frac{203}{3}n + 17n^2 + \frac{4}{3}n^3. \end{align*}$$

Exactly the same sort of analysis can then be applied to the second subsequence. I’ll leave you to check it, but if I’m not mistaken, you should get $y_n = 123+\frac{257}{3}n+19n^2+\frac{4}{3}n^3$.

It’s entirely possible to sew these two formulas together to get a single formula for the original sequence. If the original sequence is $a_0,a_1,\dots$, then $x_n = a_{2n}$, and $y_n = a_{2n+1}$. Thus, $$a_{2n} = 81 + \frac{203}{3}n + 17n^2 + \frac{4}{3}n^3,$$ and $$a_{2n+1} = 123+\frac{257}{3}n+19n^2+\frac{4}{3}n^3.$$ These can be rewritten as $$a_n = 81 + \frac{203}{3}\left\lfloor \frac{n}{2} \right\rfloor + 17 \left\lfloor \frac{n}{2} \right\rfloor^2 + \frac{4}{3} \left\lfloor \frac{n}{2} \right\rfloor^3$$ when $n$ is even, and $$a_n =$ $123 + \frac{257}{3} \left\lfloor \frac{n}{2} \right\rfloor + 19 \left\lfloor \frac{n}{2} \right\rfloor^2 + \frac{4}{3} \left\lfloor \frac{n}{2} \right\rfloor^3$$ when $n$ is odd. Note that $18-(-1)^n$ is $17$ when $n$ is even and $19$ when $n$ is odd. Similarly, $230-27(-1)^n$ is $203$ when $n$ is even and $257$ when $n$ is odd, and $102-21(-1)^n$ is $81$ when $n$ is even and $123$ when $n$ is odd. Thus, the two expressions can be combined to yield $$a_n = 102-21(-1)^n + \frac{230-27(-1)^n}{3}\left\lfloor \frac{n}{2} \right\rfloor + (18-(-1)^n)\left\lfloor \frac{n}{2} \right\rfloor^2 + \frac{4}{3}\left\lfloor \frac{n}{2} \right\rfloor^3.$$ Finally $\left\lfloor \frac{n}{2} \right\rfloor = \frac{n}{2}+\frac{(-1)^n-1}{4} = \frac{2n-1+(-1)^n}{4}$; you can substitute this into the expression for $a_n$ and simplify to get an expression of the form $a_n = p(n)+(-1)^nq(n)$ for some polynomials $p$ and $q$.

This is certainly not the most efficient way to go about solving the problem, but it does show how you could have reduced the problem to two problems of a more familiar type.

share|improve this answer
    
Can you even read yourself? This is reaaaaaaaaaaally heavy. Put some spacing, it'll sound less crazy. –  Patrick Da Silva Aug 7 '11 at 20:10
2  
@Patrick: Yes. Apparently at least two others could as well. But if you like, I can certainly convert some of it to display lines. –  Brian M. Scott Aug 7 '11 at 20:57
    
Thank you both Patrick and Brian I fully appreciate your answers. –  Adi Dani Aug 7 '11 at 21:51
    
Now you're talking! Good answer. +1 –  Patrick Da Silva Aug 8 '11 at 7:00
    
After simplifying Brian formula for general term we get $a_n=\frac{1}{24}(4n^3+102n^2+812n+1989-45(-1)^n)$ –  Adi Dani Aug 8 '11 at 19:50

Define $\Delta a_n = a_{n+1} - a_n$ (which is the forward difference) and define inductively $\Delta^{(k)}a_n = \Delta^{(k-1)} a_{n+1} - \Delta^{(k-1)} a_n$ (which is the $k^{\text{th}}$ forward difference). It can easily be shown that

$$ \Delta^{(k-1)}a_n = \sum_{i=1}^{n-1} \Delta^{(k)}a_i + \Delta^{(k-1)}a_1 $$ because it is just a telescopic sum. Now consider your sequence ; beginning from the second forward difference (or the third, say fourth if you have a bad-eye), can you guess the other forward differences?

Hint : One sees that $$ \Delta^{(2)}a_n = n+1 + 15 \left( \frac{1 + (-1)^n}2 \right) $$ This gives you the sequence $2, 18, 4, 20, 6, 22, ...$

Now you have, using the above identity $$ \Delta^{(1)}a_n = \sum_{i=1}^{n-1} \Delta^{(2)} a_i + 42 = \sum_{i=1}^{n-1} \left( i+1 + 15 \left( \frac{1 + (-1)^i}2 \right) \right) + 42 $$ You can easily compute this sum if you know elementary identities on summations. (If you can't guess the second forward difference, start with the fourth, and keep using this trick until you get to the second.)

One computes and finds $$ \Delta a_n = n^2 + 8n + \frac{67}2 - \frac{15}2 \left( \frac{1+(-1)^n}2 \right). $$ I leave the computation for you as an exercise, and using the identities $$ \sum_{i=1}^k i = \frac{k(k+1)}2, \qquad \sum_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}6, \qquad \sum_{i=1}^{n-1} (-1)^i = - \left( \frac{1 + (-1)^n}2 \right) $$ you can easily find $a_n$, but I don't have the will of computing right now. =)

Hope that helps,

share|improve this answer

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.