Finding a general form $d_n$ for a recurrence relation

Question

I have the following recurrence relation

$$d_n = 2^{(1-2n)/2}d_{n-1},\qquad d_0=1,$$

for $n\in\mathbb{Z}$. Is it possible to find a general form for $n$?

After calculating a few numbers around zero I have

$$d_0 = 2^{1/2}d_{-1}$$ $$d_1 = 2^{-1/2}d_{0}=2^{-1/2}2^{1/2}d_{-1} = d_{-1}$$ $$d_2 = 2^{-3/2}d_1 = 2^{-3/2}d_{-1}$$ $$d_3 = 2^{-5/2}d_2 = 2^{-4}d_{-1}$$

But I'm not really seeing a pattern. Is this even possible?

... and do you really mean $n\in \mathbb Z$? or just $\mathbb N$? — Christopher Carl Heckman, May 15 '16 at 00:39
@ChristopherCarlHeckman Yes I mean all the integers including negatives — user2850514, May 15 '16 at 00:42

score 2 · Answer 1 · answered May 15 '16 at 00:25

2

If $$\frac{d_n}{d_{n-1}}=2^{-\frac{2n-1}{2}} $$ by multiplying all these identities for $n=1,2,\ldots, N$ we get:

$$ d_N = d_0\cdot 2^{-\frac{1}{2}\sum_{n=1}^{N}(2n-1)} = \color{red}{d_0\cdot 2^{-N^2/2}}.$$

answered May 15 '16 at 00:25

Jack D'Aurizio

353,855

But $n$ starts at $-\infty$ not $0$. – user2850514 May 15 '16 at 00:29
@user2850514: and so? The answer should be given in terms of $d_{-\infty}$?! – Jack D'Aurizio May 15 '16 at 00:31
1

@user2850514 it is possible to deliberately give one formula for $d_N$ for $N > 0,$ written as a multiple of $d_{-1}$ if you like, and another formula for $N < 0.$ Most people woul write this as a multiple of $d_0.$ – Will Jagy May 15 '16 at 00:35
@WillJagy : That would probably be best. (Note that the OP added the fact that $d_0=1$.) – Christopher Carl Heckman May 15 '16 at 00:43

score 2 · Accepted Answer · answered May 15 '16 at 03:52

Starting with $$d_n = 2^{(1-2n)/2}d_{n-1}$$ define $c_n=\log(d_n)$ and the relation becomes $$c_n=\frac{1-2n}2\,\log(2)+c_{n-1}$$ which is much simpler to build; the general solution is $$c_n=C-\frac{1}{2} n^2 \log (2)$$ Since you are given $d_0=1$, $c_0=0$, $C=0$ and then $$c_n=-\frac{1}{2} n^2 \log (2)\implies d_n=2^{-\frac{n^2}{2}}$$

Finding a general form $d_n$ for a recurrence relation

2 Answers2