0

$x_{n+1}= 2nx_n+1$, $n\geq 0$, $x_0$=0

I tried by putting $n=0, 1, 2, 3, ...$ and got $x_0= 0$, $x_1= 1, x_2= 3, x_3= 13, x_5= 79$

I have one more

2. $x_{n+1}=((n+1)/n)x_{n}+x_n+n+1, x_1=5$

I have calculated

$x_2= 17, x_3= 35.5, $

But I can't deduce the relation.

Just give a hint, it will be a great help, Thanks. :)

Kashif Faraz Shamsi
  • 173
  • Your numbers are incorrect, the sequence starts $0, 1, 3, 13, 79, 633$. To see why, look at $x_2 = 3$. That makes the next number $x_3 = 2\cdot 2\cdot x_2 + 1 = 2\cdot 2 \cdot 3 + 1 = 13$. – orlp Sep 21 '17 at 00:45

3 Answers3

2

Maple gives me (for $n \ge 1$) $$ x_n = 2^{n-1} \sqrt{e}\; \Gamma(n, 1/2)$$ where $\Gamma$ is the incomplete Gamma function. This is not an elementary function.

And btw, that should be $x_3 = 13$, $x_4 = 79$, $x_5 = 633$, ...

Robert Israel
  • 448,999
2

This is sequence A010844.

We have formulae:

$$x_n = \lfloor n! \cdot e^{\frac{1}{2}} \cdot 2^n\rfloor$$

$$x_n = \sum_{k=0}^n2^k k! \binom n k $$

$$x_n = \int_0^\infty (2u + 1)^n e^{-u}du$$

Among others. It's exponential generating function is $\dfrac{e^x}{1-2x}$.

orlp
  • 10,508
0

A linear recurrence relation of the first order, thus solvable.

Divide by the summing factor $\prod_{1 \le k \le n} (2 k) = 2^n n!$ to get:

$\begin{align*} \frac{x_{n + 1}}{2^n n!} - \frac{x_n}{2^{n - 1} (n - 1)!} &= \frac{1}{2^n n!} \end{align*}$

The left hand side telescopes nicely if you sum over $1 \le k \le n - 1$ to get:

$\begin{align*} \frac{x_n}{2^n n!} - \frac{x_1}{2} &= \sum_{1 \le k \le n - 1} \frac{1}{2^k k!} \\ x_n &= 2^{n - 1} n! \cdot x_1 + 2^n n! \cdot \sum_{1 \le k \le n - 1} \frac{1}{2^k k!} \\ &= 2^{n - 1} n! \cdot x_1 + 2^n n! \cdot \sum_{1 \le k \le n - 1} \frac{1}{2^k k!} \\ &= 2^{n - 1} n! \cdot x_1 + 2^n n! \cdot \exp_{n - 1}(1/2) \end{align*}$

Here $\exp_n(z) = \sum_{1 \le k \le n} \frac{x^k}{k!}$.

vonbrand
  • 27,812