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

learn more… | top users | synonyms (2)

3
votes
4answers
61 views

Can this recurrence relation be solved with generating functions?

I have this recurrence relation, $$a_{n+1}=\frac{n+2}{n}a_n$$ with $a_1=1$. I've already solved this using a substitution approach by letting $a_n=\dfrac{(n+1)!}{(n-1)!}b_n$. This means ...
1
vote
1answer
69 views

Recursive random draw

Let $R(n)$ be a random draw of integers between $0$ and $n − 1$ (inclusive). I repeatedly apply $R$, starting at $10^{100}$. What’s the expected number of repeated applications until I get zero?
1
vote
0answers
47 views

Probability dice game, multiple turns

Alice and Bob are playing dices, Alice begins. If the current player gets a 6, he wins. If he gets 4 ou 5, he plays again. Else, the other player plays. Let $p_n$ (resp. $q_n$) be the ...
1
vote
2answers
45 views

Help with solving this Recurrence Relation

I really need help with this question Would anyone please give a simple step-by-step on how to solve this Recurrence Relation?? $a_n = 2a_{n-1} - 2a_{n-2}$ where $a_0 = 1$ and $a_1 = 3$ It would ...
3
votes
4answers
115 views

If $T(n)= T(n-1) + 2T(n-2)$

If $T(n)= T(n-1) + 2T(n-2)$ with $T(0)=0$ and $T(1) = 1$ What is $T(n)$ (in $Θ$–notation) in terms of $n$? I am trying to solve by substitution, but I am not sure if I am doing this right, as I ...
1
vote
1answer
30 views

Recurrence relation with characteristic equation that has only 1 root and complex roots

For the recurrence relation: $f_n = 2a_{n-1} - 2a_{n-2}$ I got the characteristic equation that had complex roots: $x^2 - 2x + 2 = 0$ that gave roots $i, -i$ and I wasn't sure how to continue the ...
3
votes
3answers
62 views

Examine the convergence of a sequence $\{a_{n}\}$ which is given by $a_{1}=a>0,a_{2}=b>0, a_{n+2}=\sqrt{a_{n+1}a_{n}},n\ge 1$

I used inequality between arithmetic and geometric means to show that a sequence $\{a_{n}\}$ is bounded: $$a_{n+2}=\sqrt{a_{n+1}a_{n}}\le \frac{a_{n+1}+a_{n}}{2}$$ Solving this, I get quadratic ...
-1
votes
2answers
43 views

How to solve recurrence equation with logarithms using the Master Theorem

how do you solve this equation of recurrence? $T(1) = 1$ $T(n) = 2T(\frac{n}{3})+n*log_2(n)+1$ The problem is the term $n*log_2(n)$. Can I only consider only $n$ as it's the larger then $log_(n)$ ...
1
vote
0answers
17 views

Solving nonlinear first-order difference equation $ d_m = p_0 + p_1d_{m-1} + p_2(d_{m-1})^2 $ (extinction problem) [duplicate]

The steady-state equilibrium is $ d^* = \frac{1-p_1-\sqrt{(p_1-1)^2-4p_0p_2}}{2p_2} $. Based on a plot, I guessed the solution $ d_m = d^*(1-e^{-\alpha m}) $, which is pretty close but not correct. ...
2
votes
2answers
50 views

Sine Cosine Sequence?

Two real sequences $\{x\}$ and $\{y\}$ satisfy $$x_{n+2}=x_nx_{n+1}-y_ny_{n+1},$$ $$y_{n+2}=x_ny_{n+1}+y_nx_{n+1}.$$ Given $x_1=y_1=1/\sqrt 2$ and $x_2=y_2=1$, find closed forms of $x_n$ and $y_n$. ...
1
vote
4answers
55 views

Examine the convergence of a sequence ${a_{n}}$: $a_{n+1}=a_{n}-\sin(a_{n}),0\le a_{1}<\pi$

${a_{n}}$: $a_{n+1}=a_{n}-\sin(a_{n}),0\le a_{1}<\pi$ One way to do it is to show that the sequence is bounded and monotonous. How to show that it is bounded? If $$-1\le \sin(a_{n})\le 1$$ ...
5
votes
0answers
63 views

About the existence of a regular solution in a chaotic system

Show that for some choice of $x_1\in\mathbb{R}$, the sequence given by: $$ x_{n+1} = n-3^{x_n} $$ satisfies: $$ \lim_{n\to +\infty} x_n= +\infty. $$ I was able to prove the statement by showing ...
2
votes
4answers
88 views

Find $x_{n}$ if $x_{1}=a>0$ and $x_{n+1}=\frac{x_{1}+2x_{2}+…+nx_{n}}{n}$

Find $x_{n}$ if $x_{1}=a>0$ and $x_{n+1}=\frac{x_{1}+2x_{2}+...+nx_{n}}{n}$ I have a problem finding sum of $$x_{1}+2x_{2}+...+nx_{n}$$ I don't see the term $x_{2}$ because if $x_{1}=a$ for ...
-1
votes
1answer
22 views

How to compute the time complexity for a recurrence relationship?

I have to compute the time complexity for this recurrence relationship: T(n) = \begin{cases} c1, & \mbox{if } n\mbox{ = 1} \\ 8T(n/4) +n +c2, & \mbox{if } n\mbox{ > 1} \end{cases} Can ...
0
votes
0answers
57 views

Solving the recurrence $T(n) = 5T(n/7) +\log n$

I am trying to solve the recurrence $T(n) = 5T(n/7) +\log n$ to find the complexity of an algorithm. Although I solve this immediately with the Master Theorem if I try to solve the recursion I found ...
-1
votes
3answers
64 views

Find $n$th iterative term in recurrence relation $a_{n+2}-5a_{n+1}+6a_{n}=0$

The sequence $(a_{n})_{n\in \mathbb{N}}$ is given by recurrence relation : $$a_{1}=0,a_{2}=-6,$$ $$a_{n+2}-5a_{n+1}+6a_{n}=0\ \ (n\ge 1).$$ We get $$a_{3}=-30$$ $$a_{4}=-114$$ $$...$$ How to find ...
0
votes
2answers
32 views

Proving $T_n = 2\times 20^n + 4\times 8^n$ by mathematical induction

Given that $T_0 = 6$ and that $T_n$ satisfies the recurrence relation $$T_{n+1} = 20T_n - 8^n \times 48$$ I have the equation for any term $n$ to be; $T_n = 2\times 20^n+4⋅8^n$ I want to prove ...
2
votes
1answer
54 views

Solution of a recurrence equations

$T(1) = 1$ $T(n) = 2T(\frac{n}{3}) + n + 1$ How do you solve this equzione recurrence? I arrived at this point and then I don't know how to proceed... $2^kT(\frac{n}{3^k}) + ...
1
vote
0answers
30 views

Discrete time Pure-Birth process with population fraction

I would like to solve difference equations for a pure-birth process, where the rate of adding new nodes depends on the fraction of population. $$x_i(t+1)-x_i(t)=\alpha ...
-1
votes
1answer
35 views

Derivation of Properties of Associated Laguerre Polynomial

1.How to prove Rodrigues formula for Associated Laguerre Polynomial? 2.How to show they are orthonormal in the interval (0,infinity)? Also I want to find normalization constant? 3.How to prove ...
0
votes
0answers
24 views

Solving simultaneous recurrences

I've been reading about characteristic equations for recurrence relations and I was wondering how one would solve a simultaneous recurrence, such as $$f(n) =c_1g(n-1) +c_2f(n-1)+ c_3$$ $$g(n) = ...
0
votes
0answers
15 views

Simulating non-stationary ARMA model

I'm trying to simulate the recurrence relation: $x_t = \frac 32x_{t-1} - \frac 12x_{t-2} + w_t - \frac 12w_{t-1} + \frac 14 w_{t-2}$ in R but the relation is non-stationary since the coefficient in ...
0
votes
0answers
9 views

How to determine if this recurrence relation is non-stationary?

I think that the recurrence relation below is non-stationary as the coefficient 1.8 > 1 which seems to be one of the recurring conditions I've seen for the AR(1) model stationarity. $x_t = 1.8 * ...
4
votes
1answer
88 views

Showing that a recursively defined sequence is decreasing.

A colleague of mine is interested in finding out how to show the following: Prove that the sequence $(a_n)$ defined by ...
1
vote
1answer
59 views

Solution of differential equation - We find only one

I want to find all the solutions of the form $y(x)=x^m \sum_{n=0}^{\infty} a_n x^n, x>0 (m \in \mathbb{R})$ of the differential equation $x^2 y''+ xy'+x^2y=0$. I have tried the following: Since ...
1
vote
1answer
31 views

Looking for help in regard to Series solutions with ordinary points (ODE)

I have a question that is in regard to the final answer that one is to get when solving some ODE questions via series. I am having some confusion on what if I am doing is correct/ why it is or is not ...
2
votes
1answer
30 views

Optimizing an asymptotic recurrence relation with two recursive terms

I have a recurrence relation that looks like this: $T(n) = 2 T(c n) + T((1-c)n) + O(1)$ The base case is just $T(b) = 1$ when $b \leq 1$. I'm trying to figure out the best value of $c \in (0, 1)$ ...
1
vote
2answers
73 views

How to solve the difference equation $u_n = u_{n-1} + u_{n-2}+1$

Given that: $$ \begin{equation} u_n=\begin{cases} 1, & \text{if $0\leq n\leq1$}\\ u_{n-1} + u_{n-2}+1, & \text{if $n>1$} \end{cases} \end{equation} $$ How do you solve this ...
0
votes
2answers
40 views

Limit of a sequence defined by a non-linear recurrence relation

How can one find the limit for the sequence $\{x_n\}^{+\infty}_{n=0}$ where $$x_0 = 0, x_1 = 1, x_{n+1} = \dfrac{x_n + nx_{n-1}}{n+1}$$ By computing the values I came to the conclusion that it ...
0
votes
2answers
87 views

Simplifying recurrence relation $T_{n+1}=20T_n-48\times 8^n$

So I have the recurrence relation $$T_{n+1}=20T_n-8^n48.$$ For $T_0 = 6$, the first terms are $72$, $1056$, $18048$. I've seen a few worked examples for simplifying other recurrence series, but I'm ...
4
votes
1answer
40 views

How to determine the generating function?

So I have $$\overset{*}{F} = \overset{*}{F}_{n-1} + \overset{*}{F}_{n-2} + g(n)$$ where $\overset{*}{F}$ is NOT a Fibonacci number for $n \geq 2$. $g(n)$ is any function $g: \mathbb{N} \to ...
3
votes
2answers
177 views

Proof by induction that $x_n>2$ where $x_{n+1}=\frac{2x_n^2 +4x_n -2}{2x_n+3}$

The sequence $x_1$ $x_2$ $x_3$..... is such that $x_1=3$ and $$x_{n+1}=\frac{2x_n^2 +4x_n -2}{2x_n+3}$$ Prove by induction that $x_n>2$ for all $n$. First I proved the base case using $n=1$ as ...
1
vote
2answers
51 views

Wolfram alpha giving wrong result on recurrence?

I have the recurrence$$a_{n+2}-a_n=1$$ The answer I got was $a_n=A+B(-1)^n+\frac n 2$, while WolframAlpha is giving me $a_n=A+B(-1)^n+\frac n 2- \frac 1 4$. Although when I plug them in the ...
1
vote
1answer
88 views

Finding the limit of a recursively defined sequence (recurrence relation). Specifically and generally

Whilst reading Goldrei's Classic Set Theory, I have come across a recursively defined sequence $a_0=0, a_1=1, a_n=\frac{1}{2}\left(a_{n-1} + a_{n-2} \right) $ The first few terms of which are: $0, ...
9
votes
2answers
136 views

Does equation $f(g(x))=a f(x)$ have a solution?

Suppose $g: [0,1] \to [0,1]$ is a strictly increasing, continuously differentiable function with $g(0)=0$ and $g(1) < 1$, and $a \in (0,1)$. Is there a function $f:[0,1] \to \mathbb{R}$ such that ...
1
vote
2answers
43 views

A non-homogeneous recurrence of Fibonacci sequence

I am working on Fibonacci sequence (recursively) But the hack is that I have the following non-homogeneous version: $$F_n =F_{n-1} +F_{n-2} +g(n)$$ Where: $F_1=g(1)$ $F_0=g(0)$ I have to use: ...
1
vote
3answers
71 views

Finding particular solution when solving recurrence relation

I have a question about how to find the particular solutions when trying to solve recurrence relations. For example, trying to solve $$ a_{n+2} = -4a_n + 8n2^n $$ I begin with finding the roots in ...
1
vote
0answers
19 views

Lines and planes-recursive formula

A family of $n$ lines is drawn in the plane such that each pair of lines cross and no $3$ dinstinct lines have a point in common Let $r(n)$ denote the number of regions into ...
1
vote
0answers
58 views

How I can make a proof to this conjecture if it is possible?

Is there someone who can show me the way helping me to proof this conjecture. If it's not open, at a least show me links or papers which to be helpful. Conjecture: Assume $c > 0$ and that an ...
0
votes
1answer
19 views

Explanation of Linear Nonhomogeneous Recurrence Relations Problem

$$5\times 3^n=v_{n+2}-6v_{n+1}+9v_n$$ $$=C(n+2)^23^{n+2}-6C(n+1)^23^{n+1}+9Cn^23^n$$ $$=18C3^n$$ Can anyone explain to me how he got $18C3^n$. I've been simplifying the 2nd step but haven't gotten ...
0
votes
1answer
28 views

Recurrence equation $f(g\cdot x)/f(x)=t$

I am trying to solve equation $\frac{f(g x)}{f(x)}=t$ and I'm out of ideas. Any suggestions? In my problem, $f$ is a continuous and weakly increasing function.
0
votes
1answer
19 views

Looking for a “nice” Recurrence relation…

I'm want to build a game (with steps) that the solution have a Recurrence relation, i.e. - to solve the game you have to move from point A to point B, from point B to point C...(kind of a maze). Of ...
1
vote
1answer
30 views

Step by step Linear Reccurence

Can someone explain to me in a little bit more detail how you can get to this point. I know its explained here but i'm trying to apply the way he did this problem to this one \begin{equation*} ...
2
votes
1answer
62 views

How to find the recurrence relation from a given polynomial?

Consider the formal power series: $A(x)=\sum a_nx^n$. and $A(x)= \frac{8+14x-50x^2}{1-7x^2+6x^3}$ I am trying to derive a recurrence relation, Is there a general method for doing it? Please help, ...
0
votes
1answer
27 views

Quick Factoring/Multiplying with recursion question

I am wondering if anyone can help to shed some light on something that I think should be very easy but I dont quite understand. In my textbook, how does author make this conclusion, From $$ ...
4
votes
2answers
38 views

How many ways to stack $n$ boxes of 4 colours so that no $2$ blue boxes are consecutive.

Let $X_n$ denote the number of ways to stack red, white and blue and green boxes, find the ways to count the ways of stacking n boxes, with no consecutive blue boxes. My attempt: Let $X^R_n$ denote ...
3
votes
1answer
51 views

How do I find an analytic solution to this recursive function?

I was playing with some recurrence relations, and I ended up with this a long nested function. How can I generalize the following relationship: $$ f_n = a + \frac{b}{f_{n-1}} $$ $$ f_1 = a + ...
0
votes
0answers
29 views

how to solve T(n)=T(Logn)+O(1)

Given That $T(1)=1$ Solve following recurrence function $T(n)=T(\log n)+O(1)$ I know the answer is $\log^* n$ but don't know how to prove it. What I tried: $\log(n)+\log(n-1)+\log(n-2)+...+1 = ...
4
votes
2answers
72 views

Name for the following set of polynomials

I have the following set of polynomials defined by $$P_n(x) = \sum^n_{k = 0} \frac{n!}{k!} x^k, \quad x \geqslant 0.$$ The first few are \begin{align*} P_0 (x) &= 1\\ P_1 (x) &= 1+x\\ P_2 (x) ...
0
votes
1answer
40 views

Recursive Equation Indexing

I'm trying to write a recursive equation/formula with all natural numbers as input but I need to exclude every number ending in a $4$ or $9$ ($n= 5i-1$, $i \in \Bbb N)$ and exclude all numbers $n= ...