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

learn more… | top users | synonyms

0
votes
1answer
73 views

Help with hairy recurrence relation

There's so much going on here I don't know where to start: $$ d_{t} = d_{t - 1} + \left(\frac{1}{r}\right)v_{t - 1} $$ $$ v_{t} = x_t + v_{t - 1} - \left(\frac{f^2}{r}\right) (4\pi^2 d_{t - 1} + D ...
1
vote
1answer
85 views

Asymptotic behaviour of $f(x) =f(\sqrt{x}) + \sqrt{x}$

I stumbled about this recursive function today: $$f_n = f_\sqrt{n} + \sqrt n$$ I tried to solve it with substitution ($m = \log_2 n, \quad g_{2^m} = g_{2^{m/2}} + 2^{m/2}$), but I have a bad feeling ...
6
votes
2answers
873 views

Solving recurrence relation of form $T(n/2 + c)$

It is obvious that the Master Theorem cannot be applied to the recurrences of the following form: $T(n) = 4T(n/2 + 2) + n$ Since I am only interested in the $\theta$ bound of the recurrence and not ...
1
vote
4answers
434 views

What is generally the strategy for converting recurrence to closed form?

Consider the Fibonacci sequence (as an example) \begin{align*} f(n) &= f(n-1) + f(n-2) \\ f(0) &= 0\\ f(1) &= 1 \end{align*} How do you convert this to the closed form ...
1
vote
0answers
41 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) $$ ...
6
votes
1answer
151 views

Prove that every element of $a_{n+2013}=\frac{a_{n+1}a_{n+2}…a_{n+2012}+1}{a_n}$ is an integer

Given $\displaystyle a_1=a_2=\cdots=a_{2013}=1$ and $\displaystyle a_{n+2013}=\frac{a_{n+1}a_{n+2}\cdots a_{n+2012}+1}{a_n}$. Prove that $a_{n+2013}\in\mathbb{N}$ for all $n\in\mathbb{N}$. I ...
0
votes
2answers
45 views

Based on a sequence of numbers in a recurrence relation, how can one make a reasonable guess what the underlying degree is?

I am wondering if there's some tip for guessing the degree of a function or if it really is just a guess (assuming one doesn't know all the inner workings of what produced the number in the first ...
1
vote
3answers
329 views

How to solve recurrence equation $f(n) = f(n-5) + f(n-10)$?

How to solve recurrence equation $f(n) = f(n-5) + f(n-10)$? For something like fibonacci sequence $f(n+1) = f(n) + f(n-1)$ I can solve for the quadratic equation $x^2-x-1=0$ then $f(n) = A x_1 + ...
3
votes
1answer
44 views

Could you please check if this substitution is right so far?

The question: Use resubstitution to solve the following recurrence equation: $$T(n) = 2T(n-1) + n;\; n \ge2\text{ and }T(1) = 1.$$ So far I have this: $$\begin{align}T(n) &= 2T(n-1) + n\\ ...
2
votes
2answers
54 views

What are some strategies for creating linear recurrence relationships?

For instance if I have a string of numbers outputted from some function $f(1), f(2), f(3), \ldots, f(n)$ that can be expressed in the form of $f(n) = af(n-10) + bf(n-9) + \cdots+ jf(n-1)$ etc (It ...
0
votes
2answers
272 views

Different recurrence relations that model the same problem

I'm trying to solve the following counting problem, but my answer is different from the textbook's: Find a recurrence relation for the number of n-digit ternary sequences that have the pattern "012" ...
2
votes
3answers
396 views

How to solve second degree recurrence relation?

For first degree recurence relation it is as simple as $f(n)=a^n\cdot f(0)+b\dfrac{a^n-1}{a-1}$. But how do you solve second degree? For example $$f(n)=\begin{cases} 1,&\text{for }n=1\\ ...
17
votes
3answers
454 views

Counting binary sequences with no more than $2$ equal consecutive numbers

I invented the following problem, but I can't solve it. There are $n$ $1$'s and $n$ $0$'s and my question is what is the number of ways to arrange them avoiding $3$ equal consecutive numbers. So for ...
1
vote
1answer
116 views

An exponential recurrence

Is there any way to solve the recurrence $$x[n+1]=(x[n]+1)2^{x[n]+1}-1$$ I know how to solve recurrences with z-transforms, but it doesn't look like that technique will yield anything useful here. ...
5
votes
5answers
345 views

The sum $\sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j$

A recent answer of mine to a question on Math Overflow includes the sum $$S(n,k,x) = \sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j,$$ where $\left\{ j \atop k \right\}$ is a Stirling number ...
1
vote
1answer
66 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\}$ ...
3
votes
0answers
240 views

Two variable recurrence relations

I'm interested in solving the following type of problem... Starting with a recurrence relation in multiple variables, for example: $$ v_{i-1,j} + v_{i,j+1} + v_{i+1,j} + v_{i,j-1} = 4v_{i,j}$$ with ...
1
vote
1answer
97 views

Closed form or upper bound for recursively defined sequence

Is there a closed form of the following sequence: $$u_0 = 2$$ $$u_{n+1} = s_n^2-s_n, \;s_n = \sum_{k=0}^{n} u_k$$ If not, I would like to have an upper bound. By looking at the numbers I guessed ...
1
vote
1answer
1k views

How to find recurrence relation for this problem?

How to find a recurrence relation for F(n) the number of ways to make n cents change using only pennies, nickels(5cents), and dimes(10cents)... So for 9 cents, there are 6 ways, which are ...
0
votes
2answers
924 views

Recurrence relation for the number of ternary trings containing 2 consecutive zeros vs not containing

Find a recurrence relation for the number of ternary strings of length n that contain a pair of consecutive Os The answer to this can be found quite easily to be: ...
1
vote
0answers
104 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 ...
5
votes
1answer
185 views

How to solve this recurrence relation $a_{n+2} = \sqrt{a_{n+1}\cdot a_{n}}$?

I am trying to solve the recurrence: $$ a_{n+2} = \sqrt{a_{n+1}\cdot a_{n}} $$ but here is a problem for me. After few steps I have this: $$ a_n^2 = a_{n-1}\cdot a_{n-2} $$ and I don't now what to do ...
3
votes
1answer
1k views

What are linear homogeneous and non-homoegenous recurrence relations?

According to my book, linear homogeneous of order k is expressed this way: $$A_0a_n+A_1a_{n-1}+A_2a_{n-2}+\cdots+A_ka_{n-k}=0$$ While a linear non-homoegeous of order k is this way: ...
1
vote
2answers
1k views

Recurrence T(n) = T(n-1) + T (n/2) + 1

I am try to find the solution to the recurrence T(n) = T (n-1) + T(n/2) + 1 Whats I have done: ...
3
votes
2answers
341 views

We define a sequence of rational numbers {$a_n$} by putting $a_1=3$ and $a_{n+1}=4-\frac{2}{a_n}$ for all natural numbers. Put $\alpha = 2 + \sqrt{2}$

We define a sequence of rational numbers {$a_n$} by putting $a_1=3$ and $a_{n+1}=4-\frac{2}{a_n}$ for all $n \in \mathbb N$. Put $\alpha = 2 + \sqrt{2}$ (a) Prove by induction on n, that $3 \le a_n ...
0
votes
1answer
60 views

$Re[f(x + n i)] = 0$ and $f(z)$ is not periodic

Let $z$ be a complex number and $f(z)$ an entire function such that For $x$ real and $n$ any integer. $Re[f(x + n i)] = 0$ and $f(z)$ is not periodic. What are typical examples of such $f(z)$ ? Is ...
2
votes
2answers
394 views

How to solve this recurrence relation: $T(n) = 4\cdot T(\sqrt{n}) + n$

I was trying to solve this recurrence $T(n) = 4T(\sqrt{n}) + n$. Here $n$ is a power of $2$. I had try to solve like this: So the question now is how deep the recursion tree is. Well, that is ...
0
votes
1answer
185 views

recurrence and fibonacci [closed]

could someone possibly help me with a proof. prove $a_n = F_{2n-1}$ for fibonacci numbers and a recurrence relation where $a_1 = 1$ $a_2 = 2$ $a_3 = 5$ $a_4 = 13$ $a_5 = 34$ 89,233,610,1597 ...
0
votes
1answer
67 views

recurrence work [duplicate]

Possible Duplicate: Recurrence relation, Fibonacci numbers could someone possibly help me prove. thankyou. $(a)$ Consider the recurrence relation $a_{n+2}a_n = a^2 _{n+1} + 2$ with $a_1 = ...
1
vote
2answers
144 views

How to solve recurrence relation

How do I solve the recurrence relation in terms of $f_0$? $$f_{n+k} = -\frac{f_n}{(n+a+k)(n+b+k)}$$ where $a$ and $k$ are fixed. No idea what to do in this case due to the fact that the difference is ...
7
votes
2answers
689 views

Recursive Integration over Piecewise Polynomials: Closed form?

Is there a closed form to the following recursive integration? $$ f_0(x) = \begin{cases} 1/2 & |x|<1 \\ 0 & |x|\geq1 \end{cases} \\ f_n(x) = ...
1
vote
4answers
3k views

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

Solve the recurrence $T(n) = 2T(n-1) + n$ where $T(1) = 1$ and $n\ge 2$. The final answer is $2^{n+1}-n-2$ Can anyone arrive at the solution.
1
vote
2answers
2k views

Solve the recurrence relation:$ T(n) = \sqrt{n} T \left(\sqrt n \right) + n$

$$T(n) = \sqrt{n} T \left(\sqrt n \right) + n$$ Master method does not apply here. Recursion tree goes a long way. Iteration method would be preferable. The answer is $Θ (n \log \log n)$. Can ...
1
vote
2answers
119 views

Solve the recurrence $T(n) = 2T(\frac{n}{2}) + \frac{n}{\log(\log n)}$

I've been trying to solve this recurrence relation in my advance algorithms paper. I've found that the Master method doesn't work. I tried using an iterative method up to an extent, and then ...
0
votes
1answer
214 views

recurrence relation of integral

Consider the integral defined by $$\displaystyle{ I_k( \phi) = \int_0^{\pi} \frac{ \cos(k\theta) - \cos( k \phi) }{ \cos \theta - \cos\phi} d \theta} $$ (a) Show that $I_k( \phi) $ satisfies the ...
3
votes
0answers
58 views

An interesting partial recurrence equation

What is the closed form solution to the following partial recurrence relation? $$f(k,n) = \sum\limits_{t=0}^{m}f(k-t, n-1),$$ where $ m \geq 0$ is some fixed parameter. The boundary values are ...
2
votes
1answer
655 views

Recurrence relation, Fibonacci numbers

$(a)$ Consider the recurrence relation $a_{n+2}a_n = a^2 _{n+1} + 2$ with $a_1 = a_2 = 1$. $(i)$ Assume that all $a_n$ are integers. Prove that they are all odd and the integers $a_n$ and $a_{n+1}$ ...
0
votes
1answer
286 views

How to solve this recurrence $T(n)= 7 T (n/2) + 2 \log (n)$?

Solve this recurrence equation $T(n)= 7T (n/2) + 2 \log (n)$? Could you please help me to solve it because I have been stuck on it for 2 nights. Thanks in advance.
0
votes
2answers
704 views

converting a recursive formula into a non-recursive formula.

We found a recursive formula for the following problem: For any positive integer $n$, let $b(n)$ be the number of ways that you can write $n$ as a sum using only the numbers 1, 2, and 3 where the ...
1
vote
0answers
177 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 ...
3
votes
1answer
382 views

Explicit Formula Given a Recursion

Suppose we have a function $f$ such that for positive integers $n \ge1$ and $f(0)=0$ and $f(1)=1$ we have: i) $f(2n + 1) = 2f(n) + 2$ ii) $f(2n) = f(n) + f(n − 1) + 2$ What is the generating ...
1
vote
0answers
73 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 ...
14
votes
1answer
4k views

Odd and even numbers in Pascal's triangle-Sierpinski's triangle

Moderator Note: At the time that this question was posted, it was from an ongoing contest. The relevant deadline has now passed. I recently learned that when the Pascal's triangle is reduced ...
0
votes
2answers
108 views

convert generating function to recurrence

How do we convert generating function to a recurrence: Lets say we have this function \[ x\mapsto x\cdot \frac{8+2x-2x^2}{1-6x-3x^2+2x^3} \] how do we get it back to a recurrence?
2
votes
1answer
34 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 fibonaci series . I know its ...
1
vote
2answers
185 views

How to come up with a recurrence relation?

In general what are some things you can do to come up with a recurrence relation for something? I've had it covered in a course in combinatorics that I took, but our professor would always say "you ...
4
votes
3answers
191 views

Maximum based recursive function definition

Does a function other than 0 that satisfies the following definition exist? $$ f(x) = \max_{0<\xi<x}\left\{ \xi\;f(x-\xi) \right\} $$ If so can it be expressed using elementary functions?
1
vote
4answers
85 views

Solving a simple recurrence.

This isn't a homework question, but it is a problem in my textbook. Given $T(n) = T(n-1) + n$, show that $T(n) = O(n^2)$ My approach: Given $T(n) = T(n-1)$ Need to show $T(n) = cn^2$, where $c ...
5
votes
4answers
195 views

Finding the general term of two related recurrence relations

I'm trying to find the general term of the recurrence relations $\quad a_{n+1}=a_n+\text hb_n$ $\quad b_{n+1}=b_n-\text ha_n $ $\quad a_0=0, \quad b_0=1$ I tried finding the terms, ...
14
votes
2answers
431 views

Solving the recurrence relation $a_n=\frac{a_{n-1}^2+a_{n-2}^2}{a_{n-1}+a_{n-2}}$

I would like to know if there is a way to get the recurrence relation $$a_n=\frac{a_{n-1}^2+a_{n-2}^2}{a_{n-1}+a_{n-2}},\qquad (a_1=1,a_2=2)$$ in closed form, or if there is no such way, how one could ...