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

learn more… | top users | synonyms (2)

0
votes
2answers
26 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: ...
0
votes
3answers
31 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 ...
2
votes
1answer
70 views
+50

Result of a $2D$ random walk with position dependent probabilities

I was just wondering about $2D$ random walks when I got the idea of a position dependent $2D$ random walk: A man is initially at $(x,y)$ and can move in a line parallel to the X and Y-axis only. ...
4
votes
2answers
58 views

How to solve linear, second order ODE with Frobenius method with a difficult recurrence relation?

The ODE in question is: $$4xy''+2y'+y=0$$ Shifting the power series of each term so that they are all raised to the power $(n+r)$ will yield this recurrence relation: $$a_{n+1}={a_n\over ...
5
votes
0answers
125 views
+50

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

I'm trying to find a closed form expression to the following recurrence relation: \begin{align} &a_k(0) = 0, \quad \forall k\geqslant 1; \\ &a_k(1) = 1, \quad \forall k\geqslant 1; \\ ...
0
votes
1answer
33 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
1answer
36 views

How to find Difference equation of this block diagram. PLEASE HELP! [on hold]

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?
1
vote
0answers
16 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
49 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
14 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
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 ...
0
votes
1answer
20 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
21 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
50 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
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 = ...
0
votes
1answer
26 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 ...
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
48 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
50 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) ...
4
votes
2answers
47 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. ...
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
436 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
177 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
56 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
51 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
270 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
24 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
41 views

A question on generating function

How to find the generating function of $\binom{2n}{n}$?
0
votes
0answers
44 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
vote
0answers
36 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
206 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
27 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 ...