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

learn more… | top users | synonyms (2)

4
votes
1answer
1k views

Solving a recurrence relation with the characteristic equation

I have some trouble solving this due to not seeing the steps to be able to feed it into the characteristic equation. $$T(n) = 4T(n-2) +n + 2^nn^2\ \text{with}\ \ T(0)=0,\ T(1)=1$$ (don't have to ...
5
votes
3answers
3k views

I have a problem understanding the proof of Rencontres numbers (Derangements)

I understand the whole concept of Rencontres numbers but I can't understand how to prove this equation $$D_{n,0}=\left[\frac{n!}{e}\right]$$ where $[\cdot]$ denotes the rounding function (i.e., ...
14
votes
6answers
1k views

How to solve this recurrence relation? $f_n = 3f_{n-1} + 12(-1)^n$

How to solve this particular recurrence relation ? $$f_n = 3f_{n-1} + 12(-1)^n,\quad f_1 = 0$$ such that $f_2 = 12, f_3 = 24$ and so on. I tried out a lot but due to $(-1)^n$ I am not able to ...
1
vote
3answers
185 views

Can Master Theorem be applied on any of these?

1) $T(n) = 6T(n/2) + 2^{3 \log(n)}$ 2) $T(n) = 8T(n/2) + \frac{n^3}{(\log(n))^4}$ 3) $T(n) = 9T(n/3) + n(\log(n))^3$ Can the complexity for these be calculated with the Master Theorem? I am not sure ...
1
vote
4answers
437 views

Solving a recurrence of polynomials

I am wondering how to solve a recurrence of this type $$p_1(x) = x$$ $$p_2(x) = 1-x^2$$ and $$p_{n+2}(x) = -xp_{n+1}(x)+p_{n}(x).$$ I am wondering, how could one solve such a recurrence. One way ...
26
votes
4answers
2k views

A stronger version of discrete “Liouville's theorem”

If a function $f : \mathbb Z\times \mathbb Z \rightarrow \mathbb{R}^{+} $ satisfies the following condition $$\forall x, y \in \mathbb{Z}, f(x,y) = \dfrac{f(x + 1, y)+f(x, y + 1) + f(x - 1, y) +f(x, ...
17
votes
5answers
969 views

Find a closed form for this sequence: $a_{n+1} = a_n + a_n^{-1}$

Today, we had a math class, where we had to show, that $a_{100} > 14$ for $$a_0 = 1;\qquad a_{n+1} = a_n + a_n^{-1}$$ Apart from this task, I asked my self: Is there a closed form for this ...
8
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.
4
votes
2answers
172 views

recurrence relation $f(n)=5f(n/2)-6f(n/4) + n$

I've been trying to solve this recurrence relation for a week, but I haven't come up with a solution. $f(n)=5f(n/2)-6f(n/4) + n$ Solve this recurrence relation for $f(1)=2$ and $f(2)=1$ At first ...
6
votes
2answers
377 views

unorthodox solution of a special case of the master theorem

I am asking for references regarding a special case of the master theorem. This theorem seems to appear quite a lot on this site, prompting me to study it in more detail, e.g. see my posts here and ...
3
votes
3answers
195 views

Recurrence relation by substitution

I have an exercise where I need to prove by using the substitution method the following $$T(n) = 4T(n/3)+n = \Theta(n^{\log_3 4})$$ using as guess like the one below will fail, I cannot see why, ...
2
votes
1answer
776 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}$ ...
4
votes
2answers
1k views

Fibonacci, tribonacci and other similar sequences

I know the sequence called the Fibonacci sequence; it's defined like: $\begin{align*} F_0&=0\\ F_1&=1\\ F_2&=F_0+F_1\\ &\vdots\\ Fn&=F_{n-1} + F_{n-2}\end{align*}$ And we ...
5
votes
3answers
183 views

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

How can I solve the recurrence relation $$T(n)=2T\left(\frac n2\right)+\frac{n}{\log n}$$? I am stuck up after few steps.. I arrive till $$T(n) = 2^k T(1) + \sum_{i=0}^{\log(n-1)} ...
2
votes
4answers
340 views

can one derive the $n^{th}$ term for the series, $u_{n+1}=2u_{n}+1$,$u_{0}=0$, $n$ is a non-negative integer

derive the $n^{th}$ term for the series $0,1,3,7,15,31,63,127,255,\ldots$ observation gives, $t_{n}=2^n-1$, where $n$ is a non-negative integer $t_{0}=0$
7
votes
3answers
1k views

Solving a Recurrence Relation/Equation, is there more than 1 way to solve this?

1) Solve the recurrence relation $$T(n)=\begin{cases} 2T(n-1)+1,&\text{if }n>1\\ 1,&\text{if }n=1\;. \end{cases}$$ 2) Name a problem that also has such a recurrence relation. The ...
14
votes
2answers
1k views

Explicit formula for Bernoulli numbers by using only the recurrence relation

It is not hard to show, by induction on $m\in\mathbb N$, that there exist a sequence $(B_n)_{n\geq0}$ of rational numbers such that ...
7
votes
5answers
482 views

How does one find a formula for the recurrence relation $a_{1}=1,a_{2}=3, a_{n+2}=a_{n+1}+a_{n}?$

I am self-studying Discrete Mathematics, and I have two exercises to solve. Find a formula for the following recurrence relation: (translated from Portuguese) a) $a_{1}=3,a_{2}=5, ...
2
votes
1answer
288 views
1
vote
1answer
240 views

Establishing formula from recurrence

Can anyone tell me how do we establish a formula from a given recurrence relation? Take the example of $f(n) = 2f(n-1) + 1$, $n \in \mathbb{Z^+}$, $f(1) = 1$ When I write out the first few values, it ...
4
votes
1answer
116 views

Recurrence $a_n = \sum_{k=1}^{n-1}a^2_{k}, a_1=1$

This seems like a really straightforward recurrence. I wrote out the first few terms: $1,1,2,6,42,1806$... It seems to grow faster than $n!$ but slower than $n^n$. Any suggestions about the closed ...
3
votes
2answers
436 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 ...
1
vote
2answers
139 views

Solving the recurrence $T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{2}\log(n)$

Please help me solve the recurrence $$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{2}\log(n) $$
53
votes
3answers
1k views

How prove this nice limit $\lim_{n\to\infty}\frac{a_{n}}{n}=\frac{12}{\log{432}}$

Nice problem: Let $a_{0}=1$ and $$a_{n}=a_{\left\lfloor n/2\right\rfloor}+a_{\left\lfloor n/3 \right\rfloor}+a_{\left\lfloor n/6\right\rfloor}.$$ Show that ...
13
votes
3answers
211 views

For $x_{n+1}=x_n^2-2$, show $\lim_{n\to\infty}\frac{x_n}{x_0x_1\cdots x_{n-1}}=2$

Suppose $x_0:=2\sqrt{2}$ and $x_{n+1}=x_n^2-2$ for $n\ge1$. We have to show $$\lim_{n\to\infty}\frac{x_n}{x_0x_1\cdots x_{n-1}}=2$$ Establishing convergence is pretty direct but I'm having trouble ...
16
votes
3answers
742 views

prove $\sqrt{a_n b_n}$ and $\frac{1}{2}(a_n+b_n)$ have same limit

i am given this problem: let $a\ge0$,$b\ge0$, and the sequences $a_n$ and $b_n$ are defined in this way: $a_0:=a$, $b_0:=b$ and $a_{n+1}:= \sqrt{a_nb_n}$ and $b_{n+1}:=\frac{1}{2}(a_n+b_n)$ for all ...
13
votes
5answers
423 views

Solve the sequence : $u_n = 1-(\frac{u_1}{n} + \frac{u_2}{n-1} + \ldots + \frac{u_{n-1}}{2})$

For a physical model I am trying to solve this sequence: $$\begin{align*} u_1 &= 1 \\ u_2 &= 1-\left(\frac{u_1}{2}\right) \\ u_3 &= 1-\left(\frac{u_1}{3} + \frac{u_2}{2}\right) \\ u_4 ...
7
votes
2answers
930 views

Proof of clockwise towers of Hanoi variant recursive solution

This is from one of the exercises in "Concrete Mathematics", and is something I'm doing privately, not homework. This is a variant on the classic towers of Hanoi, where all moves must be made ...
1
vote
1answer
179 views

An issue with approximations of a recurrence sequence

By trying to give an approximation to a given recurrence sequence I encountered a problem. To be more precise I have a method but it fails if the right condition is not met and I wonder how I should ...
3
votes
1answer
216 views

How to solve this recurrence Relation - Varying Coefficient

Sir,I have two questions related to this recurrence relation. It has been messing with me for long. Because of this I couldn't proceed my work for some time .This contains a polynomial term n+2 in ...
3
votes
3answers
536 views

expansion of $\cos^k(\theta)$

Does any body know a expansion of : $\cos^k(\theta)$ in function of $\cos$ and/or $\sin$ but without power? For example : $\cos^2(\theta)=\frac{1}{2}(\cos(2\theta)+1)$, but i would want a ...
9
votes
2answers
2k views

Evaluating the limit of a sequence given by recurrence relation $a_1=\sqrt2$, $a_{n+1}=\sqrt{2+a_n}$. Is my solution correct?

Problem The sequence $(a_n)_{n=1}^\infty$ is given by recurrence relation: $a_1=\sqrt2$, $a_{n+1}=\sqrt{2+a_n}$. Evaluate the limit $\lim_{n\to\infty} a_n$. Solution Show that the sequence ...
3
votes
2answers
639 views

Solving for the closed term solution of a third order recurrence relation with real constant coefficients

How would you solve for the closed term form of $a(n)$ given the general form of the third order linear homogenous recurrence relation with real constant coefficients. ...
2
votes
2answers
314 views

Solving recurrences with boundary conditions

I'm trying to follow CLRS ("Introduction to Algorithms") and I just hit a question in a practice assignment I found online that I just can't make any sense of. Consider this problem: Show that ...
0
votes
1answer
261 views

Recurrence relation using the master theorem $ T(n) = 4T(n/2) + n^2 \log n$

I am trying to solve the following recurrence relation using the master theorem: $ T(n) = 4T(n/2) + n^2 \log n$ So: $a=4 ,b=2, f(n)=n^2\log n$ , then $n^{\log_2 4}=n^2 $ Now i know that $n^2 \log n ...
4
votes
2answers
1k views

Inductive proof of the closed formula for the Fibonacci sequence [duplicate]

Fibonacci numbers $f(n)$ are defined recursively: $f(n) = f(n-1) +f(n-2)$ for $n > 2$ and $f(1) = 1$, $f(2) = 1$. They also admit a simple closed form: $$\sqrt 5 f( n ) = \left(\dfrac{1+ \sqrt ...
4
votes
1answer
374 views

$a_n=20a_{n-1}+12a_{n-2}$ recurrence relation question

Respected Sir, Please solve the below problem. Please... Consider the infinite $\displaystyle\mathbb{S}=\sum_{n=0}^{\infty}\frac{a_n}{10^{2n}}$, where the sequence $\{a_n\}$ is defined by ...
3
votes
2answers
126 views

Recurrence Master theorem

Find the asymptotic tight bound in $$ T(n) = 4T\left(\frac{n}{2}\right) + n^{2}\log n. $$ where $ \log n= \log _{2}n $ and $T(1) = 1$. I should solve this using all three common methods: iteration, ...
1
vote
2answers
1k views

Need some help with this recurrence equation

I'm self studying from a book I bought to learn more about algorithms and I've been trying most of the exercises in that book, so this is not a homework. Anyways, the relation I'm trying to solve is ...
1
vote
2answers
212 views

Finding the asymptotic behavior of the recurrence $T(n)=4T(\frac{n}{2})+n^2$ by using substitution method

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T\left(\frac{n}{2}\right)+n^2$$ My guess is $T(n)$ is $\Theta (n\log n)$ (and I am sure about it ...
22
votes
2answers
476 views

How to calculate $\sum_{n=1}^\infty\frac{(-1)^n}n H_n^2$?

I need to calculate the sum $\displaystyle S=\sum_{n=1}^\infty\frac{(-1)^n}n H_n^2$, where $\displaystyle H_n=\sum\limits_{m=1}^n\frac1m$. Using a CAS I found that $S=\lim\limits_{k\to\infty}s_k$ ...
9
votes
2answers
1k views

Linear homogeneous recurrence relations with repeated roots; motivation behind looking for solutions of the form $nx^n$?

If we have a linear homogeneous recurrence relation, such as $t_{k+1}=4t_k-4t_{k-1}$, and attempt to find solutions of the form $t_n=x^n$ for some $x \in \mathbb{R} \setminus \{0\}$, we obtain the ...
17
votes
1answer
229 views

Show that $\lim\limits_{n\to\infty}\frac{a_1+a_2+\dots+a_n}{n^2}$ exists and is independent of the choice of $a$

Suppose $f:\mathbb{R}\to\mathbb{R}$ has period 1, and for some $q\in(0,1)$: $$|f(x)-f(y)|\leq q|x-y|\quad \forall x,y$$ Let $g(x)=x+f(x)$, for any $a\in\mathbb{R}$,define the following sequence: ...
9
votes
1answer
262 views

What is a good asymptotic for $f_n = f_{n-1}+\ln(f_{n-1})$?

Let $f_0=2$ and $f_n=f_{n-1}+\ln(f_{n-1})$. What is a good asymptotic to the sequence $f_n$? With good I mean much better than $f_n \sim \dfrac{3n \ln(2)\ln(n)}{2}$.
8
votes
4answers
171 views

Help with a recurrence with even and odd terms

I have the following recurrence that I've been pounding on: $$ a(0)=1\\ a(1)=1\\ a(2)=2\\ a(2n)=a(n)+a(n+1)+n\\ a(2n+1)=a(n)+a(n-1)+1 $$ I don't have much background in solving these things, so I've ...
2
votes
5answers
289 views

Solving the recurrence $t(n)=(t(n-1))^2 + 1$

I am trying to solve the following recurrence relation: \begin{align*} t(1) & = 1, \\ t(n) & =(t(n-1))^2 + 1. \end{align*} I need to prove that $t(n)= k^{2^{n}}$ for some constant $k$. What is ...
13
votes
1answer
5k 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 ...
19
votes
2answers
964 views

Probability of a random binary string containing a long run of 1s?

For some fixed $n$, let $p_n$ be the probability that a random infinite binary string contains a run of consecutive $1$s, containing $n$ more $1$s than the total number appearing before the run. For ...
8
votes
3answers
776 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) = ...
3
votes
1answer
111 views

Generating and solving recurrence relations

I am trying to do this question but don't know where to go from here: The question: For $n\ge1$ let $t_n$ be the number of ways to tile the squares of a 2xn checkerboard using 1x2(which can be rotated ...