1
$\begingroup$

Some days ago, I made a question here about a common term for recursive sequence. I gained very good solutions. Thanks again.

Today, I was thinking of a general case which is given below.

Assume $p$ is a prime number, and let $a_1=1$. For $n\geq 2$, we have

$$a_n=\begin{cases} p\times a_{n-1} & \text{if }\ \ n=pk\\ p\times a_{n-1}+1 & \text{if }\ \ n=pk+1\\ p\times a_{n-1}+2 & \text{if }\ \ n=pk+2\\ \vdots\\ p\times a_{n-1}+p-1 & \text{if }\ \ n=pk+p-1\\ \end{cases}$$

where $k\in \{0,\ 1,\ 2,\ \cdots\}$. We note that $a_0$ does not exist. we are considering consider $k=0$ to define the amounts $a_2, \ a_3,\ \cdots, \ a_{p-1}$.

Just to see, I am writing some terms of the sequence here:

$$1,\ p+2,\ p(p+2)+3,\ p(p(p+2)+3)+4, \ \cdots = $$

$$1, \ p+2,\ p^2+2p+3,\ p^3+2p^2+3p+4,\ \cdots $$

I appreciate any help in advance.

$\endgroup$
  • $\begingroup$ For $p=2$ the sequence is $1,2,5,10,21,42,43,...$ and then for $n\geq 2$ we have $a_{2 n}=2^{n-2}\cdot 11-1$ and $a_{2 n-1}=a_{2 n}/2.$ $\endgroup$ – DanielWainfleet Jun 27 '16 at 2:18
1
$\begingroup$

$$\sum_{i=1}^n(i\mod p)p^{n-i}$$

You can split it into parts of size $p$ to simplify it further.

To find $\displaystyle\sum_{i=1}^mip^{m-i}$, all you have to do is find $\sum p^k$ and then differentiate both sides with respect to $p$.


$\displaystyle\sum_{i=0}^{n-1}p^i=\frac{p^n-1}{p-1}$

$\displaystyle\sum_{i=0}^{n-1}ip^{i-1}=\frac{np^{n-1}(p-1)-(p^n-1)}{(p-1)^2}=\frac{(n-1)p^n-np^{n-1}+1}{(p-1)^2}$

$\displaystyle\sum_{i=0}^{n}ip^{i-1}=\frac{np^{n+1}-(n-1)p^n+1}{(p-1)^2}$

$\displaystyle\sum_{i=0}^{n}(n-i)p^{n-i}=\frac{np^{n+1}-(n-1)p^n+1}{p(p-1)^2}$

$\displaystyle\sum_{i=0}^{n}ip^{n-i}=n\left(\frac{p^{n+1}-1}{p-1}\right)-\frac{np^{n+1}-(n-1)p^n+1}{p(p-1)^2}=\frac{np^{n+3}-np^{n+2}-np^{n+1}-(n-1)p^n+1}{p(p-1)^2}$


$\displaystyle\quad\sum_{i=1}^n(i\mod p)p^{n-i}$

$\displaystyle=\sum_{i=0}^n(i\mod p)p^{n-i}$

$\displaystyle=\sum_{k=0}^{\left\lfloor\frac np\right\rfloor}\sum_{i=0}^p ip^{n-kp-i}+\sum_{i=0}^{n-p\left\lfloor\frac np\right\rfloor} ip^{n-\left\lfloor\frac np\right\rfloor p-i}$

$\displaystyle=\cdots$

$\endgroup$
  • $\begingroup$ It is nice solution. I got and just a question, do you think it is possible to find a direct solution? I mean a solution that does not contain the part $(i \mod p)$ $\endgroup$ – Majid Jun 27 '16 at 0:48
  • $\begingroup$ @Majid I already provided the steps for you to do so. $\endgroup$ – Kenny Lau Jun 27 '16 at 6:28
  • $\begingroup$ Thank you so much Kenny! Perfect. $\endgroup$ – Majid Jun 27 '16 at 10:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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