# Define $1+x+x^2+\cdots+x^n$ recursively

Let $$x \neq 1$$ be a real number. Define the following sum recursively: $$1+x+x^2+\cdots+x^n$$

My attempt:

Using summation notation we can write the sum as $$\sum_{i=0}^{n} x^i$$. Now define $$\sum_{i=0}^{0}x^i:=x^0=1 \quad \text{and} \quad \sum_{i=0}^{n}x^i:=\sum_{i=0}^{n-1}x^i+x^n$$ It seems to me correct because if we use the definition for $$n=3$$, then $$\sum_{i=0}^{3}x^i=\sum_{i=0}^{2}x^i+x^3=(\sum_{i=0}^{1}x^i+x^2)+x^3=((\sum_{i=0}^{0}x^i+x)+x^2)+x^3=1+x+x^2+x^3$$ In other words, we reach the base case. However, I'm unsure if this is correct. I might have misunderstood what a recursive definition is.

• Isn’t it simpler to just say $f(n) = x^n + f(n-1)$? Sep 22 '20 at 17:10
• $f(n+1)=xf(n)+1$. Sep 22 '20 at 17:11

As I mentioned as a comment, we can define the recurrence:

$$\begin{equation*} f(n) = \left\{ \begin{array}{ll} x^n + f(n-1) & \quad n > 0 \\ 1 & \quad n = 0 \end{array} \right. \end{equation*}$$

for all $$n \in \mathbb{N}_0$$.

• Using your recurrence you can also define $f(-1)=0$ since $f(0)=1=1+f(-1)$ Sep 22 '20 at 21:02

I think this is the best you can do: $$a_n=x\cdot a_{n-1} + 1$$

With $$a_0=1$$

$$f_n(x) = 1 + x + \ldots + x^n.$$

It can be rewriten as

$$f_n(x) = 1 + x\cdot\left(1 + \ldots + x^{n-1}\right),$$

or

$$f_n(x) = 1 + x\cdot f_{n-1}(x)$$

for $$n>0$$ and

$$f_0(x) = 1.$$

• You forgot the base case $f_0(x) =1$ Oct 2 '20 at 10:14
• True, I edited the answer. Oct 3 '20 at 14:18