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

learn more… | top users | synonyms (2)

5
votes
0answers
59 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
86 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
50 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
61 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
53 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
22 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
19 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
11 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
8 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
87 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
56 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
0answers
23 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
71 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
34 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
83 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
38 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
173 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
50 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
2answers
75 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
133 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 ...
0
votes
2answers
42 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
45 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
18 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
54 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
28 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
61 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 ...
2
votes
1answer
41 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
27 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
67 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
36 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= ...
4
votes
2answers
51 views

Triangular Array's Recursive Formula Breakdown

I have the following polynomials: $$1$$ $$z-1$$ $$z^2-2z+3$$ $$z^3-3z^2+9z-15$$ $$z^4-4z^3+18z^2-60z+93$$ $$z^5-5z^4+30z^3-150z^2+465z-725$$ $$...$$ They are generated both recursively and explicitly. ...
0
votes
0answers
23 views

Find $v_k$ the probability of absorption at $N$ if the walk starts at $S_0=k$ for $0 \leq k \leq N$

Supose that $(S_n)_{n\geq0}$ is a random walk on $\{0,1,2,\dots,N\}$ with up prbability of $p$ and down probability of $(p-1)$. Find $v_k$ the probability of absorption at $N$ if the walk starts at ...
2
votes
2answers
20 views

Proving two Recurrence Relations

I encountered this problem in the International baccalaureate Higher Level math book, and my teacher could not help. If anyone could please take the time to look at it, that would be great. I need ...
0
votes
0answers
22 views

Lyapunov function for discrete dynamical system

Consider the ODE \begin{equation} \dot{x}(t) = h(x(t)), \end{equation} where $h: \mathbb{R}^d \to \mathbb{R}^d$ is a continuously differentiable map. Let $x^*$ be an asymptotically stable ...
0
votes
1answer
20 views

First order differential equation to standard form conversion

I need to convert the following differential equation to standard form. $$ T_n = 2 T_{n-1}+1 $$ (not quite sure how to really format it properly) I was thinking it is $$ T_n - 2T_{n-1} - 1$$ If ...
1
vote
2answers
32 views

Series definied by recurrence relation

Define a sequence recursively by $$\large{a_1 = \sqrt{2},a_{n+1} = \sqrt{2 + a_n}}$$ (a) By induction or otherwise, show that the sequence is increasing and bounded above by 3. Apply the monotonic ...
0
votes
0answers
57 views

Solve the following recurrence relation in two variables

How to solve this recurrence $$S(m,n)=S(m,n-1)+S(m-1,n-1)+S(m-1,n)$$ with base conditions $$S(1,1)=3,\; S(0,n)=S(m,0)=1.$$ This recurrence came up when I tried to solve this problem: Find the ...
0
votes
2answers
55 views

solve recurrence relation: comparisons to construct binary search tree with maple

I would like to solve the recurrence relation for the average number of comparisons necessary to the construction of a binary search tree. the recurrence is $$ i(n) = n - 1 + \frac{2}{n} ...
0
votes
1answer
83 views

A recurrence for a combinatorial problem

$N$ balls are tossed into $n$ boxes independently. Each ball has a $1/n$ chance of falling into any box.$$P_{N,n}(k):= Pr\{exactly\:k\:empty\:boxes\:after\:N\:balls\:thrown\:into\:n\:boxes\}$$ Show ...
0
votes
1answer
48 views

Problem with Recurrence Relations

A particle P executes a random walk on the line above such that when it is at point $n$ ($1 \leq n \leq 9$, $n$ a non-negative integer), it has a probability of $0.4$ of moving to $n+1$ and a ...
7
votes
1answer
146 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 ...