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

learn more… | top users | synonyms (2)

1
vote
1answer
14 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
30 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
25 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 $$ ...
0
votes
0answers
13 views

How to find asymptotic of this kind of function?

Let $f:\mathbb{R_+}^2 \to \mathbb{R_+}$ defined as follows: $f(x,y)=1$ where $x\in [0,1]$ and $y\in [0,1]$. Otherwise, it follows the recurrence relation $$f(x,y) = \sup\left\{w(y_0)g(x) + ...
4
votes
2answers
37 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
36 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
25 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 = ...
-1
votes
0answers
22 views

How to find Difference equation of this block diagram. PLEASE HELP!

Can anyone please help me with this question. Like for part b), it says i need to convert all the z terms to negative powers. How do i do that and how do i find the transfer function?
0
votes
1answer
45 views

Chair arrangement problem - recurrence

Say we have $n$ chairs in a row. We will settle down $k$ guests on those chairs. It is not possible to settle down two people beside each other on two consecutive chairs. How many ways are there to ...
4
votes
2answers
46 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
30 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
41 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
20 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
12 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
18 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
28 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
45 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 ...
1
vote
2answers
42 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
53 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 ...
6
votes
1answer
115 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 ...
2
votes
0answers
37 views

How many entries in the sequence $x_n$ given by recursion $x_1=1\ ,\ x_{n+1}=p_{x_n}$ are known?

The sequence $x_n$ with the recursion $x_1=1\ ,\ x_{n+1}=p_{x_n}$ , where $p_k$ denotes the $k-th$ prime, has the following values : ...
1
vote
3answers
87 views

nth element of recurrence relation

I need to find explicit equation, that will give me n-th element of this recurrence: $$ a_0=0\\ a_1=3\\ a_{n+2}=a_{n+1} + 2a_{n} $$ I know, that I can use generating functions and difference ...
1
vote
4answers
176 views

Proof the golden ratio with the limit of Fibonacci sequence [duplicate]

Let $F_n=F_{n-1}+F_{n-2}$ the Fibonacci numbers, and $\phi=\frac{1+\sqrt5}{2}$ The exercise asks me to prove that: $\lim\limits_{n \to \infty}\frac{F_{n+1}}{F_n}=\phi$. Sorry as can be proceed??
0
votes
0answers
12 views

Name of this function

Is there a name for the following function? $f(x,y) = \begin{cases} y+1, & \text{if $x=0$} \\ f(x-1,1), & \text{if $y=0$} \\ f(x-1, f(x-1,y-1)), & \text{otherwise} \end{cases}$
0
votes
0answers
22 views

Recurrence relation to calc words with odd number of letter A

I have to define the recurrence relation that allow to calc the number of words with length $n$ in the set $\{A,B,C,D,E\}$ with odd number of $A$. I almost solved it. I get to this conclusion: ...
1
vote
0answers
38 views

A question on generating function

How to find the generating function of $\binom{2n}{n}$?
0
votes
0answers
43 views

Solving $T(n)=2T(n-1)$

I have the following recurrence relation: $$T(n)=2T(n-1)$$ I would like to find the running time of the algorithm. I tried the following, having in mind that the correct solution is $$O(2^n)$$ So ...
-1
votes
0answers
23 views

How to find the perodicity of a recurrence relation [closed]

Please help me in finding out the periodicity of this recurrence relation: $$f(x+1)=(af(x)+b) \pmod {m}$$ $f(1)=d$ where $d,a,b,m$ are integers and range of $f(x)$ are also integers.
6
votes
1answer
50 views

The number of series over $\{0,1,2\}$ without repeating numbers

What is the number of series over $\{0,1,2\}$ with length $n$ without repeating the same number one after the other ($22$ is not allowed but $101$ is), that does not begin and end with the number $2$. ...
1
vote
0answers
35 views

How to solve nonlinear recurrence relation (quadratic)

Please help me solve this weird recurrence relation. This is not really standard quadratic, so I'm totally confused. I tried with logarithm (but 8 is excess), tried writing this recurrence in one ...
4
votes
1answer
73 views

Is there a nice recurrence relation for $n^n$

I know there is a nice equation for $n!$, but is there one for $n^n$? I was thinking you could get it with the fact $n^n=a^{n\log_an}$ but I can't seem to make the needed jump. Edit: It was suggested ...
0
votes
2answers
28 views

Linear Recurrences

I was working on linear recurrence... But I am having trouble with it. $a_0 = 1; a_1 = 2; a_k = 4a_{k-1} - 2a_{k-2}$ I found $a_2$ which is $$4a_1 - 2 a_0=4\cdot2 - 2\cdot 1 = 6$$ I found $a_3$ ...
-1
votes
0answers
26 views

Solve the following difference equation: $u_{n+1}=2u_n+n$ with $u_0=1$

Solve the following difference equation: $u_{n+1}=2u_n+n$ with $u_0=1$ Since $u_{n+1}=2u_n+n$, then $u_{n}=2u_{n-1}+(n-1)$. Thus, $v_n:=u_{n+1}-u_{n}=2(u_n-u_{n-1})+1$. So we can break this down ...
4
votes
0answers
266 views

Series expansion for $x_n=x_{n-1}+\log \left(x_{n-1}\right)$

$x_0=2,\ x_n=x_{n-1}+\log \left(x_{n-1}\right)\quad$ has a series expansion about $1.$ Since $x_0=2,$ $(x_0-1)^k=1,$ so the recurrence can be written, up to the first $5$ terms as \begin{align} ...
0
votes
3answers
36 views

First order difference equation. Solve $u_{n+1}=3u_n+2$.

First order difference equation. Solve $u_{n+1}=3u_n+2$ with $u_0=0$ My notes are very sparse on this topic, so I need some help solving what should be an easy question. I would really appreciate ...
1
vote
1answer
20 views

Find a formula for $\langle X_n\rangle$ which is defined recursively as follows

$X_1=a$, $X_2=b$ and $X_{n+2}=(X_n+X_{n+1})/2$ Find a formula for $\langle X_n\rangle$ valid for each $n\in\mathbb N$. I wrote a few terms in this sequence and tried to derive a formula. But I ...
2
votes
4answers
205 views

Showing a particular recurrence is constant

A sequence, $ ( a_n ) _ { n \in \mathbb{N}} $, is constructed by selecting a value of $ a_0$, and then successively forming the following elements from the equation. $$ a_n = 2- \frac12 a_ { n- 1} ...
-1
votes
0answers
15 views

Select k non overlapping rectangles in a $n \times m$ grid

We are given a given a $n \times m$ grid with $nm$ points. We have to select $k$ rectangles(obviously with corners lying at lattice points) such that no $2$ of them overlap. We can give a recurrence ...
1
vote
1answer
29 views

Select $k$ non overlapping segments from $n$ points

We have $n$ points , say labeled from $1$ to $n$. We have to select $k$ segments from it so that no $2$ overlap. One possible solution would be by using a recurrence relation $f(k,n)=\sum ...
1
vote
1answer
40 views

Solving This Particular Recurrence Equation

Let $\lambda \in \mathbb{R}$. Is there any way I could solve this recurrence? $$ a_k=-\dfrac{\lambda^2 a_{k-4}}{k(k+1)} $$ where $$ a_0\in\mathbb{R} \quad\quad a_1\in\mathbb{R} \quad\quad ...
1
vote
2answers
45 views

Solve the recurrence $a_n=7a_{n-1}-10a_{n-2}$ where $a_{0}= 3$ and $a_{1}=3$

Solve the recurrence $a_n=7a_{n-1}-10a_{n-2}$ where $a_{0}= 3$ and $a_{1}=3$ how can a $a_{0}$ and $a_{1}$ both equal $3$?
0
votes
3answers
31 views

Linear recurrence

Having trouble solving this type of question, I can solve it when the equation equates to 0 however when it equates to something like $5(3)^n$ I get stuck. here's the question: $$(1) \quad u_n - ...
0
votes
4answers
82 views

Solve the reccurence $a_n= 4a_{n−1} − 2 a_{n−2}$

Solve the recurrence $a_n = 4a_{n−1} − 2 a_{n−2}$ Not sure how to solve this recurrence as I don't know which numbers to input to recursively solve?
3
votes
2answers
43 views

What happens to a system of difference equations when A is non-diagonalizable?

Suppose I have a system of linear difference equations $$ \mathbf{x}_{n+1} = A \mathbf{x}_n \>.$$ If $A$ is diagonalizable, then it can be shown that the system asymptotically approaches ...
0
votes
1answer
42 views

Find a linear reccurrence relation where a(n) is the number of subsets of {1,2,3,…,n} not containing three consecutive numbers.

Find a linear constant coefficient for the recurrence relation $a(n)$ where $a(n)$ is the number of subsets of $\{1,2,3,\dots,n\}$ not containing three consecutive numbers. So $a(n)$ must have a ...
0
votes
0answers
12 views

Is it valid recurrence for Master Theorem? $T(n)=T(n/2)+2^n$

So in class we did the following $T(n)=T(n/2)+2^n$ -----> Case 3 $ O(2^n)$ When I read in the internet it says that I cannot apply Master Theorem if f(n) is not polynomial. So what is the true ...
2
votes
1answer
30 views

Master Theorem for solving recurrences question

Who can explain to me why $$T (n) = 4T (n/2) + n/ \log n \Longrightarrow T (n) = Θ(n^2) \tag{Case 1}$$ But for $$T (n) = 2T (n/2) + n/ \log n$$ ⇒ Master Theorem does not apply (non-polynomial ...
4
votes
1answer
35 views

How many strings of $\{0,1,2,3\}$ of length $n$ are there such that $0$ appears exactly once and $1$ appears an even number of times?

How many strings of length $n$ of the digits $\{0,1,2,3\}$ are there such that $0$ appears exactly once and $1$ appears an even number of times? My attempt: define $a_n$ to be a sequence of such ...