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

learn more… | top users | synonyms (2)

4
votes
1answer
2k 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 ...
12
votes
3answers
6k 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., ...
10
votes
5answers
3k views

Proof of Convergence: Babylonian Method $x_{n+1}=\frac{1}{2}(x_n + \frac{a}{x_n})$

a) Let $a>0$ and the sequence $x_n$ fulfills $x_1>0$ and $x_{n+1}=\frac{1}{2}(x_n + \frac{a}{x_n})$ for $n \in \mathbb N$. Show that $x_n \rightarrow \sqrt a$ when $n\rightarrow \infty$. I have ...
14
votes
6answers
2k 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 ...
5
votes
3answers
734 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)} ...
1
vote
3answers
280 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
610 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 ...
7
votes
2answers
3k 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 ...
32
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, ...
20
votes
5answers
1k views

Closed form for the sequence defined by $a_0=1$ and $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 myself: Is there a closed form for this ...
10
votes
4answers
7k views

What is the solution to the following recurrence relation with square root: $T(n)=T (\sqrt{n}) + 1$?

This looks like a question asked earlier, but it isn't. $$T(n)=\begin{cases} T (\sqrt{n}) + 1 \quad & \text{ if } n>1 \\ 1 & \text{ if }n=1\end{cases}$$ My professor gave this to me in ...
8
votes
2answers
399 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 ...
5
votes
2answers
16k views

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

How can I solve the recurrence relation $T(n) = 2T(n/2) + n\log n$? It almost matches the Master Theorem except for the $n\log n$ part.
18
votes
2answers
2k 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 ...
6
votes
1answer
607 views

convoluted recurrence: $f(2n)=f(n)+f(n+1)+n, f(2n+1)=f(n)+f(n-1)+1$

For the recurrence relation: $f(0)=1$ $f(1)=1$ $f(2)=2$ $f(2n)=f(n)+f(n+1)+n\ \ \ (\forall n>1)$ $f(2n+1)=f(n)+f(n-1)+1\ \ \ (\forall n\ge 1)$ (the first numbers of the sequence are: 1, 1, 2, ...
7
votes
2answers
924 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 ...
8
votes
4answers
7k 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.
1
vote
4answers
7k 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 ...
3
votes
2answers
265 views

Find the asymptotic tight bound for $T(n) = 4T(n/2) + n^{2}\log n$

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, ...
8
votes
3answers
2k 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 ...
3
votes
3answers
463 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
1k 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}$ ...
1
vote
1answer
353 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
2answers
2k 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 ...
9
votes
4answers
515 views

Help with a recurrence with even and odd terms [duplicate]

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\ \ \ (\forall n>1)\\ a(2n+1)=a(n)+a(n-1)+1\ \ \ (\forall n\ge 1) $$ I don't have much ...
4
votes
3answers
4k views

Recurrence relation (linear, second-order, constant coefficients)

Q1. Find the general solution to the difference equation $$ a_{n} - 4a_{n-1} + 3a_{n-2} = 6 $$ Q2. Solve the difference equation $$ a_{n} - a_{n-1} - 2a_{n-2} = 0, a_0 = 2, a_1 = 4 $$ I am ...
2
votes
4answers
349 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$
1
vote
2answers
331 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 ...
11
votes
5answers
1k views

How to deduce a closed formula given an equivalent recursive one?

I know how to prove that a closed formula is equivalent to a recursive one with induction, but what about ways of deducing the closed form initially? For example: $$ f(n) = 2 f(n-1) + 1 $$ I know ...
13
votes
2answers
3k 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 ...
7
votes
5answers
643 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, ...
4
votes
1answer
397 views
3
votes
4answers
963 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 ...
3
votes
2answers
7k views

Linear Homogeneous Recurrence Relations and Inhomogenous Recurrence Relations

I'm having some difficulty understanding 'Linear Homogeneous Recurrence Relations' and 'Inhomogeneous Recurrence Relations', the notes that we've been given in our discrete mathematics class seem to ...
5
votes
1answer
125 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 ...
4
votes
2answers
597 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 ...
3
votes
1answer
3k views

$T(n) = 4T({n/2}) + \theta(n\log{n})$ using Master Theorem

I am trying to solve the following recurrence relation using the master theorem: $$T(n) = 4T({n/2}) + \theta(n\log{n})$$ So: $a = 4$, $b = 2$, and $f(n) = n\log{n}$ So we are comparing: ...
2
votes
2answers
198 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) $$
0
votes
2answers
1k views

Total Time a ball bounces for from a height of 8 feet and rebounds to a height 5/8

I am trying to solve the following problem. Let's say a ball is dropped from a height of $8$ feet and rebounds to a height $\frac{5}{8}$ of its previous height at each bounce keeps bouncing ...
0
votes
2answers
4k 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
64
votes
3answers
2k 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 ...
20
votes
3answers
1k 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 ...
18
votes
1answer
298 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: ...
13
votes
2answers
2k views

Exact probability of random graph being connected

The problem: I'm trying to find the probability of a random undirected graph being connected. I'm using the model $G(n,p)$, where there are at most $n(n-1) \over 2$ edges (no self-loops or duplicate ...
13
votes
3answers
256 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 ...
9
votes
2answers
627 views

A polynomial sequence

I have a sequence of polynomials $Q_k(x, y)$, $k\geq 1$ defined recursively as follows: $Q_1=x$. There is a sequence of polynomials $p_j(y)$ of degree $j$ such that $Q_{2m}$ is of the form ...
14
votes
3answers
5k views

Solving recurrence relation in 2 variables

We already know how to solve a homogeneous recurrence relation in one variable using characteristic equation. Does a similar technique exists for solving a homogeneous recurrence relation in 2 ...
13
votes
5answers
470 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 ...
13
votes
1answer
7k 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 ...
12
votes
3answers
5k views

Why is solving non-linear recurrence relations “hopeless”?

I came across a non-linear recurrence relation I want to solve, and most of the places I look for help will say things like "it's hopeless to solve non-linear recurrence relations in general." Is ...