1
$\begingroup$

For a sequence $a$, $a_1=2$, $$a_n=\frac{n-1}{a_{n-1}}+n-1$$Express $a_n$ in terms of $n$.

I tried keep expanding, got many level of fraction until $n=1$, but I still can't see the pattern. Please help. Thank you.

  • 0
    Can you provide some context? For example, are you sure that you didn't just forget some parentheses?2012-11-03
  • 0
    @Phira: What do you mean?2012-11-03
  • 0
    Where does the recurrence come from?2012-11-03
  • 0
    $$a_n=\frac{n-1}{a_{n-1}}+n-1$$2012-11-03
  • 0
    This is the recurrence, but where did it come from? Does it give the average length of a certain algorithm? Does it give the coefficients of a power series? Do you know what the word "context" means?2012-11-03
  • 0
    This's a maths question I found somewhere.2012-11-03
  • 0
    I want to know why you think that there is a nice answer, because if this is from a book at at, say, high school level, then I would assume that you or the book have made a typo with the parentheses, if it comes from a lecture on hypergeometric functions, then the answer might be a hypergeometric function, if it comes from a problem you have thought up yourself, then there is no reason that a nice answer should exist. The fact that you answer "This's a maths question I found somewhere." gives me the impression that you prefer to be evasive instead of making it possible to get an answer.2012-11-03
  • 0
    This's some part of a maths question I found in a website. The original question is to find $a_n$ given $a_n=(n-1)(a_{n-1}+a_{n-2})$ for $n≥4$, $a_1=0,a_2=1,a_3=2$. I divide it by $a_{n-1}$ and let $b_n=a_{n}/a_{n-1}$, which gives me $b_n=(n-1)/b_{n-1}+n-1$.2012-11-03
  • 0
    Please add the original recurrence in your question. The solution of the original question are the derangement numbers. Taking the quotient was not a good idea because the quotient of the derangement numbers is not very nice.2012-11-03
  • 0
    I'll do it later, I get to go.2012-11-03

1 Answers 1

2

I doubt very much that you’re going to get anything very nice. If you do the obvious thing and begin by calculating a few values, you get this:

$$\begin{array}{rcc} n:&1&2&3&4&5&6\\\\ a_n=\frac{p_n}{q_n}:&2&\frac32&\frac{10}3&\frac{39}{10}&\frac{196}{39}&\frac{1175}{196}\\\\ p_n:&2&3&10&39&196&1175\\ q_n:&1&2&3&10&39&196\\ a_n:&2&1.5&3.\overline{3}&3.9&\sim5.025641&\sim5.994898\\\\ \end{array}$$

The last line is just to get an idea of the actual size of $a_n$, and the previous lines just give the numerator and denominator of the rational representation in the second line. It’s immediately apparent that $q_n=p_{n-1}$, and indeed if we set $a_n=\frac{p_n}{q_n}$ we have

$$a_{n+1}=\frac{n(p_n+q_n)}{p_n}\;,$$

$p_{n+1}=n(p_n+q_n)$ and $q_{n+1}=p_n$, and finally $p_{n+1}=n(p_n+p_{n-1})$.

In short, the sequence is entirely determined by the sequence $\langle p_n:n\in\Bbb N\rangle$ (where we may take $p_0=1$). This turns out to be OEIS A003048, and the entry gives the closed form

$$p_n=2n!-\left\lfloor\frac{n!+1}e\right\rfloor$$

and the exponential generating function

$$g(x)=\frac{2-e^{-x}}{1-x}\;.$$

(It is clear that $a_n\approx n$ for even moderatly large $n$.)