5
$\begingroup$

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.

$\endgroup$
2
  • 6
    $\begingroup$ Isn’t it simpler to just say $f(n) = x^n + f(n-1)$? $\endgroup$ Sep 22 '20 at 17:10
  • 7
    $\begingroup$ $f(n+1)=xf(n)+1$. $\endgroup$
    – Mark Sapir
    Sep 22 '20 at 17:11
6
$\begingroup$

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

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

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

With $a_0=1$

$\endgroup$
3
$\begingroup$

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

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

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.