Questions regarding functions defined recursively, such as the Fibonacci sequence.

learn more… | top users | synonyms (2)

9
votes
4answers
537 views

Help with a recurrence with even and odd terms [duplicate]

I have the following recurrence that I've been pounding on: $$ a(0)=1\\ a(1)=1\\ a(2)=2\\ a(2n)=a(n)+a(n+1)+n\ \ \ (\forall n>1)\\ a(2n+1)=a(n)+a(n-1)+1\ \ \ (\forall n\ge 1) $$ I don't have much ...
9
votes
1answer
385 views

How does one prove that $\zeta(3)$ is irrational?

How does one prove that $\zeta(3)$ is irrational ? I would like to know how Apery did it. In particular how a recursion gives rise to irrationality !?
9
votes
3answers
304 views

The integer $c_n$ in $(1+4\sqrt[3]2-4\sqrt[3]4)^n=a_n+b_n\sqrt[3]2+c_n\sqrt[3]4$

For non-negative integer $n$, write $$(1+4\sqrt[3]2-4\sqrt[3]4)^n=a_n+b_n\sqrt[3]2+c_n\sqrt[3]4$$ where $a_n,b_n,c_n$ are integers. For any non-negative integer $m$, prove or disprove $$2^{m+2}|c_n\...
9
votes
1answer
339 views

Recurrence equation similar to a geometric progression

I have the following recurrence relation: $$T(i) = \sqrt{T(i-1) \left(T(i+1) + k\right)},$$ with $k \geq 0$, a fixed constant. I know that when $k=0$, we have: $$T(i) = \sqrt{T(i-1) T(i+1)},$$ which ...
9
votes
0answers
82 views

How to Find the Recurrence Formula for $\int \frac{dx} {(1+\sin x)^n}$?

$$\int \frac{dx} {(1+\sin x)^n}$$ I know that I should use the following step: $$\int\frac{\sin^2(x)\, dx}{(1+\sin x)^n} +\int\frac{\cos^2(x)\, dx} {(1+\sin x)^n} $$ but here I get stuck. I do ...
9
votes
1answer
67 views

Prime Concatenation Order

Consider the following procedure. Given an integer $n \geq 2$, obtain the canonical prime factorization of $n$, i.e. $\prod_{i=1}^k p_i^{e_i}$. Take the distinct factors $p_i$ and list them in ...
9
votes
0answers
267 views

Coefficients in expansion of $(\sqrt[3]{2} - 1)^m$

In trying to solve $a^3 - 2b^3 = 1$ over the integers I came across the need to answer the question: when does $(1+ \sqrt[3]{2} + \sqrt[3]{2}^2)^n$ have no $\sqrt[3]{2}^2$ term in it's expansion (in ...
9
votes
0answers
137 views

Is this a recurrence for the characteristic sequence of composite numbers?

The characteristic sequence of composite numbers is equal to 1 if $n$ is not a prime number and equal to 0 if $n$ is a prime number, starting: $$1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1,...$$ where the ...
8
votes
4answers
7k views

How to find the closed form formula for this recurrence relation

$ x_{0} = 5 $ $ x_{n} = 2x_{n-1} + 9(5^{n-1})$ I have computed: $x_{0} = 5, x_{1} = 19, x_{2} = 83, x_{3} = 391, x_{4} = 1907$, but cannot see any pattern for the general $n^{th}$ term.
8
votes
3answers
2k views

Solving a Recurrence Relation/Equation, is there more than 1 way to solve this?

1) Solve the recurrence relation $$T(n)=\begin{cases} 2T(n-1)+1,&\text{if }n>1\\ 1,&\text{if }n=1\;. \end{cases}$$ 2) Name a problem that also has such a recurrence relation. The ...
8
votes
4answers
6k views

How to get the characteristic equation?

In my book, this succession defined by recurrence is presented: $$U_n=3U_{n-1}-U_{n-3}$$ And it says that the characteristic equation of such is: $$x^3=3x^2-1$$ Honestly, I don't understand how. ...
8
votes
2answers
642 views

Solving recurrence relations that involve all previous terms

I'm not sure if this a proper recurance relation per se but I'd be interested in the methodology in solving a recurrence relation of the following form: $Z_0 = 1$ $Z_1 = x_1$ $Z_2 = x_1Z_1 + x_2 = ...
8
votes
2answers
671 views

Reduction formula for $I_{n}=\int {\cos{nx} \over \cos{x}}\rm{d}x$

What would be a simple method to compute a reduction formula for the following? $\displaystyle I_{n}=\int {\cos{nx} \over \cos{x}} \rm{d}x~$ where $n$ is a positive integer I understand that it ...
8
votes
1answer
268 views

How to solve $ \sqrt{x^2 +\sqrt{4x^2 +\sqrt{16x^2+ \sqrt{64x^2+\dotsb} } } } =5\,$?

How to find $x$ in: $$ \sqrt{x^2 +\sqrt{4x^2 +\sqrt{16x^2+ \sqrt{64x^2+\dotsb} } } } =5 $$
8
votes
1answer
1k views

Methods to find the limit of a sequence defined by a recurrence

For a sequence defined by a formula normally the usual limit rules allows one to find its limit. But for a sequence defined by a recurrence, up to now I have only seen some refined ad hoc methods, ...
8
votes
2answers
2k views

Numerical method for finding the square-root.

I found a picture of Evan O'Dorney's winning project that gained him first place in the Intel Science talent search. He proposed a numerical method to find the square root, that gained him $100,000 ...
8
votes
2answers
243 views

Limit of the sequence $a_{n+1}=\frac{1}{2} (a_n+\sqrt{\frac{a_n^2+b_n^2}{2}})$ - can't recognize the pattern

Consider the sequence: $$a_0=x,~~~b_0=y$$ $$a_{n+1}=\frac{1}{2} \left(a_n+\sqrt{\frac{a_n^2+b_n^2}{2}} \right),~b_{n+1}=\frac{1}{2} \left(b_n+\sqrt{\frac{a_n^2+b_n^2}{2}}\right)$$ $$\lim_{n \to \...
8
votes
4answers
632 views

Closed form for a non-linear recurrence

Does equation $a_n=\sqrt{a_{n-1}+6}$ with $a_1=6$ have a closed form? I've found no linearization method. Any suggestion or hint will be highly appreciated.
8
votes
2answers
1k views

Proof of clockwise towers of Hanoi variant recursive solution

This is from one of the exercises in "Concrete Mathematics", and is something I'm doing privately, not homework. This is a variant on the classic towers of Hanoi, where all moves must be made ...
8
votes
2answers
405 views

recurrence relation $f(n)=5f(n/2)-6f(n/4) + n$

I've been trying to solve this recurrence relation for a week, but I haven't come up with a solution. $f(n)=5f(n/2)-6f(n/4) + n$ Solve this recurrence relation for $f(1)=2$ and $f(2)=1$ At first ...
8
votes
1answer
165 views

Does $a_0=0, a_1=1, a_{n+2}=2a_{n+1}-3a_n$ ever return to 1 or -1 for $n>3$?

The sequence in question is the Lucas or Generalized Fibonacci sequence A088137. It's easy to write down its generating function $\frac{x}{1-2x+3x^2}$ and an explicit formula $a_n = \frac{\sqrt{2}}{2}...
8
votes
3answers
814 views

Repertoire method for solving recursions

I am trying to solve this four parameter recurrence from exercise 1.16 in Concrete Mathematics: \[ g(1)=\alpha \] \[ g(2n+j)=3g(n)+\gamma n+\beta_j \] \[ \mbox{for}\ j=0,1\ \mbox{and}\ n\geq1 \] I ...
8
votes
1answer
170 views

Finding closed form for a generating function with different powers of $x$ in parameter

I'm working on a math/programming puzzle that involves an integer series defined as having a recurrence relating values $a(n)$ to $a(\lfloor\frac{n}{2}\rfloor)$ and $a(\lfloor\frac{n}{4}\rfloor)$. ...
8
votes
3answers
307 views

Quadratic Equation Recurrence?

So I was playing around with the following: Let $f_0(x) = x^2 - bx + c$. If $f_n(x)$ has roots $p$ and $q$ with $p > q$, then let $f_{n+1}(x) = x^2 - px + q$. The recurrence relation is rather ...
8
votes
1answer
142 views

Prove that a holonomic (p-recursive) difference equation returns only integral values

Consider the recurrence given by $(n+1)^2 a_{n+1} = (9n^2+9n+3)a_n-27n^2 a_{n-1}$ $a_0 = 1, a_1 = 3$. Clearly, $a_n$ is rational, but unexpectedly, the recurrence seems to output only integral ...
8
votes
1answer
82 views

Newton's method for square roots 'jumps' through the continued fraction convergents

I know that Newton's method approximately doubles the number of the correct digits on each step, but I noticed that it also doubles the number of terms in the continued fraction, at least for square ...
8
votes
1answer
392 views

Challenging recurrence relation problem

I am starting out with the following: $$ \frac{d^n}{dx^n}[g(x)^{f(x)}] = \sum_{c=0}^n g(x)^{f(x)-c}\lambda_{n,c}(x) $$ Therefore: $$ \frac{d^{n+1}}{dx^{n+1}}[g(x)^{f(x)}] = \sum_{c=0}^{n+1}g(x)^{f(...
8
votes
1answer
268 views

Find the general term of the sequence defined by $x_0 = 3, x_1 = 4$ and $x_{n+1} = x_{n-1}^2 - nx_n$

Question: Find the general term of the sequence defined by $x_0 = 3, x_1 = 4$ and $x_{n+1} = x_{n-1}^2 - nx_n$. Attempt: If I'm not mistaken this does not match any linear homogeneous pattern, nor ...
8
votes
1answer
157 views

What are the solutions for $a(n)$ and $b(n)$ when $a(n+1)=a(n)b(n)$ and $b(n+1)=a(n)+b(n)$?

If you have the following recurrence relations : $a(n+1)= a(n) b(n)$ $b(n+1)= a(n) + b(n) $ How do you find the form of $a(n)$ and $b(n)$ ? I suspect there isn't a closed form , but a infinit sum ...
8
votes
2answers
98 views

Closed form of a recursive relation

A sequence $\langle a_n\rangle$ is defined recursively by $a_1=0$, $a_2=1$ and for $n\ge 3$, $$a_n=\frac 12 na_{n-1}+\frac 12n(n-1)a_{n-2}+(-1)^n\left(1-\frac n2\right).$$ Find a closed form ...
8
votes
1answer
435 views

How to solve this recurrence

Solve the recurrence \[ f_{j,k}^{(l)} = \begin{cases} \left[j>k\right] j^{k-1}(j-k), &\qquad j=l \\ \\ \left[j>k+1\right] \sum_t \binom k t f_{j-1,k-t}^{(l)}, &\qquad j>l \end{cases} \...
7
votes
6answers
420 views

Finding the $n$-th derivative of $f(x) =e^x \sin x$, solving the recurrence relation

I was given a homework assignment to find a closed solution for the nth derivative of the function: $f(x) = e^x \sin x$ So far I have been able to obtain the derivative as: $f^{(n)}(x) = e^x S_n \...
7
votes
5answers
229 views

How can I find the value of $a^n+b^n$, given the value of $a+b$, $ab$, and $n$?

I have been given the value of $a+b$ , $ab$ and $n$. I've to calculate the value of $a^n+b^n$. How can I do it? I would like to find out a general solution. Because the value of $n$ , $a+b$ and $ab$ ...
7
votes
3answers
325 views

How can I rewrite recursive function as single formula?

There is following recursive function $$ \begin{equation} a_n= \begin{cases} -1, & \text{if}\ n = 0 \\ 1, & \text{if}\ n = 1\\ 10a_{n-1}-21a_{n-2}, & \text{if}\ ...
7
votes
2answers
473 views

Recurrent sequence limit

Let $a_n$ be a sequence defined: $a_1=3; a_{n+1}=a_n^2-2$ We must find the limit: $$\lim_{n\to\infty}\frac{a_n}{a_1a_2...a_{n-1}}$$ My attempt The sequence is increasing and does not have an upper ...
7
votes
5answers
646 views

How does one find a formula for the recurrence relation $a_{1}=1,a_{2}=3, a_{n+2}=a_{n+1}+a_{n}?$

I am self-studying Discrete Mathematics, and I have two exercises to solve. Find a formula for the following recurrence relation: (translated from Portuguese) a) $a_{1}=3,a_{2}=5, a_{n+1}=3a_{n}-2a_{...
7
votes
3answers
582 views

Common term for differential equations and recurrence relations

Recently I have been working with recurrence relations (mostly linear), and systems of coupled recurrence relations. I have noticed a lot of common ground with differential equations. In a way, you ...
7
votes
3answers
269 views

How can I find an explicit expression for this recursively defined sequence?

We define the sequence $(u_n)_{n=1}^\infty$by:$$u_{n+1}=1+\frac{1}{u_n}$$ How can I find the limit of this sequence as it goes to infinity? By induction, I can prove that it is bounded above and ...
7
votes
1answer
115 views

Is there any explicit formula for $x_n$?

Let $a$ be a positive real number and $(x_n)$ be the sequence given by $x_1>0,$ $$x_{n+1}=\dfrac{1}{2}\Big(x_n+\dfrac{a}{x_n}\Big).$$ We can prove that $x_n\to\sqrt{a}$ as $n\to\infty.$ My ...
7
votes
2answers
290 views

Does anyone recognise this recursion sastisfied by the Bell numbers?

I derived a recursion $$B_n=\frac{1}{n}B_0+\frac{1}{n}\sum_{k=1}^{n-1}\left[\binom{n}{k}-(-1)^{n-k}\binom{n}{k-1}\right]B_k\tag{$*$}$$ which I know should be satisfied by the moments of the unit ...
7
votes
1answer
311 views

How prove that $x_1 = x_{2000}$ implies $x_2 \ne x_{1999}$, where $x_{n+2}=\frac{x_{n}x_{n+1}+5x^4_{n}}{x_{n}-x_{n+1}}$?

Let $x_{1},x_{2},\cdots$ be real numbers, such that for $n \ge 1$: $$x_{n+2}=\dfrac{x_{n}x_{n+1}+5x^4_{n}}{x_{n}-x_{n+1}}$$ If $x_{1}=x_{2000}$, prove that $x_{2}\neq x_{1999}$. my idea $$x_{n+2}x_{...
7
votes
5answers
443 views

The sum $\sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j$

A recent answer of mine to a question on Math Overflow includes the sum $$S(n,k,x) = \sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j,$$ where $\left\{ j \atop k \right\}$ is a Stirling number ...
7
votes
6answers
123 views

If $a_{n+1}=\frac {a_n^2+5} {a_{n-1}}$ then $a_{n+1}=Sa_n+Ta_{n-1}$ for some $S,T\in \Bbb Z$.

Question Let $$a_{n+1}:=\frac {a_n^2+5} {a_{n-1}},\, a_0=2,a_1=3$$ Prove that there exists integers $S,T$ such that $a_{n+1}=Sa_n+Ta_{n-1}$. Attempt I calculated the first few values of $...
7
votes
3answers
467 views

Why computing Fatou coordinate is so hard?

I'm trying to make images of Fatou coordinate for some polynomial maps. If I'm not wrong there is no explicit general formula/method for computing Fatou coordinate near parabolic fixed point. Is ...
7
votes
4answers
386 views

How can I solve this linear recurrence relation?

My problem is: this given recurrence relation: $$y_{n+1}-\frac{n+2}{2}\cdot y_n = (n+1)(n+2)\cdot 3^n$$ for all: $n\ge 0$ and $y_0 = 0$ I need to find the explicit form and the general solution. My ...
7
votes
4answers
309 views

Limit of $x_n^3/n^2$ when $x_{n+1}=x_n+ 1/\sqrt {x_n}$ with $x_0 \gt 0$

Let $(x_n)_{n \ge 0}$ a sequence of real numbers with $x_0 \gt 0$ and $x_{n+1}=x_n+ \frac {1}{\sqrt {x_n}}$. Check the existence and find $$L=\lim_{n \rightarrow \infty} \frac {x_n^3} {n^2}$$ ...
7
votes
3answers
409 views

Solving recurrence relation: Product form

Please help in finding the solution of this recursion. $$f(n)=\frac{f(n-1) \cdot f(n-2)}{n},$$ where $ f(1)=1$ and $f(2)=2$.
7
votes
3answers
695 views

The number of length-n ternary sequences with even ones and even zeroes

Just starting to appreciate recurrence relations Let $T_n = $ number of length-n ternary sequences with an even number of ones and an even number of zeroes. $T_0 = 1$, because $0$ is an even number, ...
7
votes
3answers
134 views

Help me understanding logic behind limits of recurence relations

I was trying to understand how limits of recurence relations are working. I have one. $$a_0 = \dfrac32 ,\ a_{n+1} = \frac{3}{4-a_n} $$ So, from what i know, if this recurence relation has a limit, ...
7
votes
2answers
3k views

Inductive proof of the closed formula for the Fibonacci sequence [duplicate]

Fibonacci numbers $f(n)$ are defined recursively: $f(n) = f(n-1) +f(n-2)$ for $n > 2$ and $f(1) = 1$, $f(2) = 1$. They also admit a simple closed form: $$\sqrt 5 f( n ) = \left(\dfrac{1+ \sqrt 5}{...