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

learn more… | top users | synonyms

3
votes
1answer
74 views

Solving recurrence relation

$A(n) = A(n-1) + B(n-1)$ $B(n) = A(n-1)$ $A(1) = 2\ ,\ B(1) = 1 $ Please help to find closed form of $C(n) = A(n) + B(n)?$
17
votes
3answers
447 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 ...
0
votes
2answers
82 views

a way to solve this relation $a_n = 4a_{n-1}-4a_{n-2}+2^n$

the equation $a_n = 4a_{n-1}-4a_{n-2}+2^n$ have the homogeneous part of $a_n=A_1 n2^n + A_2 2^n$ but i dont know how to solve the particular part. my method is As $\beta(n)=2^n$ by the guessing ...
0
votes
0answers
179 views

k-dissection of a polygon with non-intersecting diagonals

I am trying to use the vertex coalescing method like the one mentioned here, page 10, to count: Number of dissections of a polygon using non-intersecting diagonals into even number of regions. I am ...
0
votes
2answers
67 views

Find the general formula of $u_n$:

Find the general formula of $u_n$: $$\begin{cases}u_1=\frac{5}{4}\\[10pt]u_{n+1}=8u_n^4-8u_n^2+1, \forall n \in \mathbb{N} \end{cases}$$
1
vote
2answers
102 views

Closed form solution for recurrence

I need to find a closed form solution for the following recurrence: $T(m) \leq T(\sqrt m) + 1$, $T(1)=1$ I honestly don't have even have an idea where to start. Help would be greatly appreciated!
1
vote
1answer
531 views

Ways to partition an n-element set

I've done a couple of searches and haven't found a solution to this here, but if I've missed it please feel free to close the question! I was wondering how many different equivalence relations I ...
0
votes
1answer
72 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
831 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
3answers
312 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 + ...
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 ...
1
vote
4answers
424 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) $$ ...
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 ...
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\\ ...
0
votes
2answers
269 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" ...
3
votes
1answer
375 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
1answer
112 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. ...
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\}$ ...
1
vote
1answer
95 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
996 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 ...
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: ...
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: ...
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
388 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 ...
3
votes
2answers
335 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
181 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
142 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 ...
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
3answers
3k views

Master Theorem for Solving $T(n) = T(\sqrt n) + \Theta(\lg\lg n)$

I'm trying to solve the recurrence relation: $$T(n) = T(\sqrt n) + \Theta(\lg \lg n)$$ My first step was to let $m = \lg n$, making the above: $$T(2^m) = T(2^{m\cdot 1/2}) + \Theta(\lg m)$$ If ...
3
votes
2answers
364 views

Solution of $T(n)=2T(n/2) + n\log(\log n)$

I am struggling to solve this equation: $$T(n)=2T(n/2) + n\log(\log n).$$ I concluded that the Master Theorem does not apply in this situation so I tried to successively substitute the terms in order ...
0
votes
1answer
207 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
57 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
626 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}$ ...
7
votes
4answers
3k views

How to find the closed form formula for this recurrence relation

$ x_{0} = 5 $ $ x_{n} = 2x_{n-1} + 9(5^{n-1})$ I have computed: $x_{0} = 5, x_{1} = 19, x_{2} = 83, x_{3} = 391, x_{4} = 1907$, but cannot see any pattern for the general $n^{th}$ term.
2
votes
2answers
84 views

Asymptotics of $nT(1) + \frac{n}{\lg5}\sum_{i=1}^{\log_5 n}\frac{1}{i}$

I am trying to find asymptotics/running time of recurrence $T(n) = 5T(\frac{n}{5}) + \frac{n}{\lg n}$. Since Master Theorem for solving the reassurances can't be used, I was able to unroll it and came ...
1
vote
0answers
172 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
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 ...
3
votes
2answers
165 views

Given $g(x)$, how to solve function recurrence $f(x)=af(\alpha x)+bf(\beta x)+g(x)$ where $\alpha\neq\beta$

If we have a recurrence like $$f(x)=af(\alpha x)+bf(\beta x)+g(x)$$ where $a,b,\alpha,\beta\in\mathbb{R}$ and $\alpha\neq\beta$ and $g(x)$ is known. How can we solve this kind of recurrence? For ...
4
votes
3answers
190 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?
0
votes
2answers
106 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?
14
votes
2answers
422 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 ...
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
181 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 ...