# I need a common term for a recursive sequence

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.

• 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.$ – DanielWainfleet Jun 27 '16 at 2:18

## 1 Answer

$$\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$

• 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)$ – Majid Jun 27 '16 at 0:48
• @Majid I already provided the steps for you to do so. – Kenny Lau Jun 27 '16 at 6:28
• Thank you so much Kenny! Perfect. – Majid Jun 27 '16 at 10:49