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

learn more… | top users | synonyms (2)

1
vote
0answers
262 views
1
vote
0answers
43 views

Recurrence with cases

$\def\left{\operatorname{left}}\def\right{\operatorname{right}}$I have the following recurrence with cases: $$ p(l, r, s) = 0.5 \cdot \left(l, r, s) + 0.5 \cdot \right(l, r, s) $$ ...
1
vote
1answer
76 views

Recurrence Relation Using Cases

How would one go about solving a recurrence relation that has different cases? The whole problem asks for Derive a formula for the number of strings of length n over the alphabet $\{0, 1, 2\}$ ...
1
vote
0answers
112 views

Cycle of remainders

Let $N, K, W$ be natural numbers If I start from $R_0$, say any integer $r_0, 0 \lt r_0 \lt N$ and proceed with: $$R_j = ( R_{j-1} + K ) \mod W,\quad j=1,2, \dots$$ (that is the remainder of the ...
1
vote
0answers
241 views

To obtain the closed-form expression of CDF and PDF from the recurrence relation

Now I have a question, in which I need to find the probability mass function and the cumulative distribution function. But now I only have the recurrence relation. Here is the details: Assume ...
1
vote
0answers
74 views

Let $f(x+1) = P(f(x),x)$ where P is a polynomial. Express $f(x)$ as an integral.

Let $x$ be a real number and $f(x)$ a real analytic function such that $f(x+1) = P(f(x),x)$ where $P$ is a given real polynomial. Express $f(x)$ as an integral from $0$ to $\infty$. As an example we ...
1
vote
0answers
35 views

What is the definition of Cauchy function associated with the differential or difference equations?

What is the definition of Cauchy function associated with the differential or difference equations? Where can I find the details?
1
vote
6answers
668 views

Solving Recurrences using Telescoping/Backwards Substitution

Specifically, $$T(n)=3T(n-1)+1; \quad T(1)=1.$$ I have \begin{align*} T(n) & = 3T(n-1)+1 \\ & = 3(3T(n-2)+1)+1 \\ & = 9T(n-2)+4 \\ & = 9(3T(n-3)+1)+4 \\ & = 27T(n-3)+13 \\ & ...
1
vote
0answers
70 views

Finding the radian of a second-order eqn

I am really confused on what to do with the value d This is the solution I have now but not sure if it is correct or not.
1
vote
0answers
160 views

two dimensional recurrence

We have the following recurrence relation for $a_{n,m}$ $a_{n,m}=4a_{n+1,m-1}+\sum_{i=0}^{n-1}\sum_{j=0}^{m}a_{i,j}a_{n-1-i,m-j}$ with the boundary condition $a_{n,0}=c_n$ for $n\ge0$ where $c_n$ ...
1
vote
0answers
196 views

Evaluating iterated sine function

Let $f(x,1)=\sin(x)$ and $f(x,i)=f(\sin(x),i-1)$ ($f$ is the iterated sine function). For arbitrary $N$,$x_0$, how quickly can $f(x_0,N)$ be computed? Answer to this question discusses ...
1
vote
0answers
202 views

Closed form expression for a recurrence relation.

Hello, any ideas for computing closed form for a recurrence relation? In an attempt to compute what the $i$-th post order element would be in terms of its in order position in a complete binary tree, ...
1
vote
1answer
173 views

How to solve a recurrence equation with non-constant coefficients?

How to solve a recurrence equation with non-constant coefficients? The equation is $$ 120(3k+1)(18k^3-21k-2)(k+2)a_{3k-6}=120(54k^4-117k^2+4)(k-1)a_{3k-5}+(k-1)^2(3k^2-2)^2k^3(k+2)(k+1)(6k^2+6k-1). $$ ...
1
vote
0answers
154 views

A recurrence relation

Motivated by a specific example, I have a rather general question to ask: suppose $a_n$ is a sequence defined by the relation $a_{n+1}=f_na_n+g_na_{n-1}$, $a_0=a>0$, $a_1=b>0$, where both $f_n$, ...
1
vote
1answer
108 views

Bivariate recurrence relation

Consider the following recurrence relation: $$A(h,0)=1\\ A(h,h)=c^h\\ A(h,r)=A(h-1,r)+(c-1)\cdot A(h-1,r-1).$$ Obviously, this is just a generalization of A008949, where $c=2$. Since I'm pretty sure ...
1
vote
0answers
244 views

non-linear delay differential equation

I'm looking for an explicit (not numeric) solution to the following non-linear delay differential equation (aka difference differential equation). It's a sort of Riccati type equation. ...
1
vote
0answers
189 views

Recurrence relation for the digits of the integer square root in binary

I was investigating a question on the Electrical Engineering Stack Exchange site, available here: ...
1
vote
0answers
209 views

Achieving the “mirror” of exponential decay

I'm working on a product that has a visual transition. I've found that applying a simple filter that results in an exponential decay (starting fast, then tapering off) is pleasing in one direction. ...
1
vote
0answers
146 views

recurrence relation of general difference polynomials

I have a sequence of difference polynomials (which I obtained by the method of finite differences) and I would like to find out if there is a recurrence relation between them. The generating function ...
1
vote
0answers
109 views

Find $G(n)$ with $n \geq 1$

Let $G(1) = 0, \ G(2) = 1$, $G(2n+1) = 2 + G(n) + G(n+1)$ and $G(2n) = 1 + G(n), \ \ n \geq 1$ Find $G(n) $ P.S: This is little problem in my problem. I tried to solve by using generating function, ...
1
vote
0answers
103 views

How to find the recurrence polynomial?

Problem: If $f$ is a polynomial with unknown roots $x_1,-x_1,x_2,-x_2\ldots,x_b,-x_b \quad (b \in \mathbb{N})$ and can be expressed as (known expansion): $$f(x)=\sum_{a=0}^{2b}f_ax^a\quad(b \in ...
1
vote
0answers
263 views

System of difference equations

Is there an effective way of finding a particular $x_n$, say $x_5$, of a system of difference equations $x_{n}=ax_{n+1}+bx_{n-1}$ where $a, b$ are constants and the $n$'s say are $\leq k$ (apart from ...
1
vote
0answers
67 views

Recurrence $A_{n+1}=A_{n}+\mathbf{E}G_n$

This looks like a straightforward recurrence, but I have an impression I made a mistake somewhere. In this equation $G_n$ is a random variable $ G_n=\left\{ \begin{array}{c c} 0 & 1-p_n \\ ...
1
vote
1answer
71 views

Applying the master theorem

State the asymptotic runtime found by the master theorem. If the master theorem does not apply state why: 1) $T(n) = $T($n/3)$ 2) $T(n)= $ $5T$($2n/5$) + $n$ 3) $T(n) = 4T(n/2) +15n^3 + 4n^2 +n+4$ ...
1
vote
2answers
111 views

Is there a method for finding the fixed point of logarithmic functions?

I am faced with this function (warning, I am not good at math) $x(t+1)=0.5 \ln x(t)+1$ initial condition = 1 . I know the fixed point is 1 because $0.5 \ln (1)+1=1$ but I wanted to know the ...
0
votes
6answers
94 views

Convergence of a sequence given by $x_{n+1}=\frac 23(x_n+1)$

A sequence $(x_n)_{n\in\mathbb N}$ is defined by $$x_0=0, \qquad x_{n+1}=\frac23(x_n+1)\text{ for }n=1,2,\dots$$ Prove that this sequence converges and find the limit. The infimum of $(x_n)$ ...
0
votes
3answers
137 views

How to show that closed form of Fibonacci number is roots ratio difference of $n^{th}$ power of roots to difference of roots of $x^2 - x - 1=0$

1.5 The Fibonacci numbers $1,1,2,3,5,...$ are defined by the recursion formula $x_{n+1} = x_n + x_{n-1}$, with $x_1 = x_2 = 1$. Prove that $(x_n, x_{n+1}) = 1$ and that $x_{n} = \frac{a^n ...
0
votes
3answers
39 views

A closed form for the recursion?

Let $x$ and $y$ be real numbers and $x < y$ Given the recursion: $m_0 = \frac{x+y}{2}$ and $m_1 =\frac{m_0+ y}{2}$, so in general, $$m_i = \frac{m_{i-1} + y}{2}$$.. What is $m_{\infty}$? thanks ...
0
votes
3answers
95 views

Fiddling with a Fibonacci-Like Sequence

Let $X\in\mathbb{Z}.$ Let $F_n$ be a sequence of positive integers given by $$F_{i+1}=F_i+F_{i-1}$$ $$F_2=X*F_1+F_0$$ I am trying to find an upper bound or (sharp) inequality of $F_i$ in terms of ...
0
votes
2answers
30 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
139 views

partitions and their generating functions and Partitions of n

A partition of an integer, n, is one way of writing n as the sum of positive integers where the order of the addends (terms being added) does not matter. p(n, k) = number of partitions of n with k ...
0
votes
3answers
137 views

Differentiate a recurrence relation

How do I calculate the derivative of an equation like: $z_n = (z_{n-1} + c)^2$ with respect to $n$ where $z_0 = 0$ and $z,c \in \mathbb{C}$ I suspect that, for a given $z$, the derivative is not ...
0
votes
3answers
142 views

A sequence is defined by: $a(1) = 1$ and $a(n + 1) = 3a(n) - 1$ for $n \ge 1$. What is $a(100)$?

A sequence is defined by: $a(1) = 1$ and $a(n + 1) = 3a(n) - 1$ for $n \ge 1$. What is $a(100)$? Solution. The first few terms of $a(n)$ are $1,2,5,14,\ldots$. The general solution to the ...
0
votes
3answers
536 views

can we use generating functions to solve the recurrence relation $a_n = a_{n-1} + a_{n-2}$, $a_1=1$, $a_2=2$?

I have this question. Can we use generating functions to solve the recurrence relation $$\begin{align*} a_1 &= 1,\\ a_2 &= 2,\\ a_n &= a_{n-1} + a_{n-2} \end{align*}$$ Thanks
0
votes
4answers
2k views

Converting an explicitly defined function to a recursive one

In studying for an exam, I had difficulty with these two questions: Give a recursive form (including bases) for the following functions. $$f(n) = 5 + (-1)^n$$ $$f(n) = n(n+3)$$
0
votes
2answers
88 views

Solve the recurrence $T(n) = 2T(n-1)+n^2$

Solve the recurrence $$T(1) = 1, T(2) = 1, T(3) = 1,T(n) = 2T(n-1)+n^2, n > 3$$ I have now, $$T(n) = 2T(n-1)+^2 $$ $$= 2(2T(n-2)+(n-1)^2+n^2$$ $$=4T(n-2)+2(n-1)^2+n^2$$ $$....$$ ...
0
votes
1answer
43 views

If $T(n+1)=T(n)+\lfloor \sqrt{n+1}, \rfloor$ $\forall n\geq 1$, what is $T(m^2)$?

$T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$ $T(1)=1$ The value of $T(m^2)$ for m ≥ 1 is? Clearly you cannot apply master theorem because it is not of the form ...
0
votes
2answers
48 views

Proof by induction that $f(1) + 2f(2) + 3f(3) + \cdots + n f(n) = f(n+1) - 1$, where $f(0) = 1$ and $f(K+1) = (K+1) f(K)$?

We've got the following function: $$f:N \rightarrow N$$ $$f(0) = 1$$ $$f(K+1) = (K+1)\times F(K)$$ How can I proof in induction the following: $$1\times f(1)+2\times f(2)+3\times f(3)+...+n\times ...
0
votes
3answers
50 views

Sequence difference equatiom

For $n \ge 2$ the terms in the sequence $a = \{1, 6, 17, 45, 118, 309, \ldots\}$ are related by the difference equation $$a_{n+2} = \boxed{\phantom{XX}} \, a_{n+1} + \boxed{\phantom{XX}} \, a_n $$ ...
0
votes
2answers
152 views

Recursive formula to the number of words length n with restrictions

Looking for recursive formula to the number of words length $n$ with the letters $A,B,C $and the following restrictions: neither $AB$ nor $CA$ can occur as a string in the word. I tried to build a ...
0
votes
1answer
926 views

Rate of Convergence for Gradient Descent (Example)

I am trying to determine the rate of convergence for $f(x,y) = 5x^2 + 5y^2 − xy − 11x + 11y$. Would anyone be able to provide guidance as to how I might go about doing this? Should I select my own ...
0
votes
2answers
161 views

Resolve this recurrence: $T(2^n) = T(2^{n-1}) + 2^n$

I need to resolve this recurrence: $$T(2^n) = T(2^{n-1}) + 2^n$$ The conditions are: Give a $\theta$ bound. In case that cannot find a $\theta$ bound, provide tight upper ($O$ or $o$) and lower ...
0
votes
2answers
187 views

Solving a weird difference equation

I'm trying to find a way to solve the following difference equation, but I have exhausted all the resources at my disposal so now I come here for guidance. The equation is the following: $$x_1 = ...
0
votes
2answers
2k views

Recurrence telescoping $T(n) = T(n-1) + 1/n$ and $T(n) = T(n-1) + \log n$

I am trying to solve the following recurrence relations using telescoping. How would I go about doing it? $T(n) = T(n-1) + 1/n$ $T(n) = T(n-1) + \log n$ thanks
0
votes
2answers
37 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
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 $$ ...
0
votes
3answers
33 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
2answers
31 views

Prove that two recursive sequences are always not zero.

I have the following recursive sequences: $x_n = x_{n-1} + 2y_{n-1} , x_1 = 1$ $y_n = y_{n-1} - x_{n-1}, y_1 = -1$ where $ x_n,y_n \in \mathbb{Z}$ I have to show that for any $n$ neither $x_n$ ...
0
votes
1answer
124 views

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

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. ...
0
votes
2answers
51 views

recurrence relations and generating functions - I need a hint

I need to find "closed form" to the recurrence relation given by: $a_{n+1} = \sum_{k=0} ^ {n} k a_{n-k}$ and $a_0 = 1$. I have tried using generating functions but it is no good. Any help would be ...