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

learn more… | top users | synonyms (2)

0
votes
1answer
18 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 ...
0
votes
1answer
15 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.
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
32 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
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 = ...
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 $$ ...
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 ...
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) + ...
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
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= ...
-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
0answers
46 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 ...
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
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
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. ...
2
votes
0answers
85 views
+50

The recurrence $a(n,k) = \sum_{0\leqslant j<n} a(n+j,k-1)$

I'm trying to find a closed form expression to the following recurrence relation: \begin{align} &a(0,k) = 0, \quad \forall k\geqslant 1; \\ &a(1,k) = 1, \quad \forall k\geqslant 1; \\ ...
4
votes
0answers
56 views

What is the explicit formula (solution) to this recursively defined binary matrix?

My question concerns the following binary matrix (call it matrix $A$). Or rather the entire family of such matrices, for some number of columns $n$ and rows $2^n$. The ellipses indicate that the ...
3
votes
1answer
434 views

Recurrence Relation, Discrete Math problem(Homework)

There is a disk, separated into n sections, as indicated in the graph. For each section, you can paint it with one color out of four: Red, Yellow, Blue, Green. The rule is adjacent sections can't have ...
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 ...
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??
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 ...
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
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 ...
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 ...
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 ...
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 ...
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$. ...
4
votes
0answers
267 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} ...
2
votes
1answer
39 views

How to find out the dependence on past terms from a recurence relation

Suppose I know the generating function.Then how do I find out the dependence of of the $n^{\text{th}}$ term on the past $k$ terms from it?? For eg : Suppose I have the Fibonacci series . I know its ...
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
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.
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 ...
3
votes
2answers
98 views

The k-th difference of the sequence $n^{k}$ is constant and equal to $k!$

Define the k-th difference of a sequence $\{a_n\}$ inductively as follows: The $1$-th difference is the sequence $\{b_n\}$ given by $b_n=a_{n+1}-a_n$ The "$k+1$"-th difference is the sequence ...
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 ...
4
votes
2answers
145 views

Optimization of parameter for recursive Cauchy sequence

I have the following recursive sequence I'm analyzing: $$V_0 = 50, V_1 = (1-10k)V_0,$$ $$V_{n+1} = (1-10k)V_n - 5kV_{n-1}$$ where $k > 0$ is a parameter that I'm investigating by running ...
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$ ...
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
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 ...
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 ...
-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 ...