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

learn more… | top users | synonyms (2)

1
vote
1answer
47 views

Prove by induction T(n) = T(⌊n/2⌋) +T(⌊7n/16⌋) + n

Prove by induction on n that T(n)=O(n), where T(0)=1, T(n) = T(⌊n/2⌋) +T(⌊7n/16⌋) + n So far I have, Base Case: n = 1 [1/2] + [7/16] + 1 T(1) = 1 Induction hypothesis: Assume that for arbitrary ...
0
votes
0answers
74 views

What is the asymptotic complexity of?

$$T(n) = \begin{cases}T\left (n/\log_2{n}\right) + 1 & n>2\\1&n\leq 2\end{cases}$$ I'm tempted to think that the answer is $\Theta(\log n)$, but the denominator decreases as $n$ decreases. ...
0
votes
0answers
23 views

Recurrence relations closed form solutions

I am looking at various recurrence relations of the form: $x_{n+2} + bx_{n+1} +cx_{n} = f(n)$ In the book I use, I have been given an algorithm on how to solve these kinds of recurrence relations ...
1
vote
2answers
47 views

Why does generating functions work? (recurrence relations)

I guess the title says it all. However, I have skimmed through several books, and while they all tell you how to use generating functions to find an expression for the n'th term of a recurrence ...
0
votes
1answer
30 views

Recurrence relations of the type $a(n,k) = a(n-1,k-1) a(n,k-1) /a(n-1,k-1)- a(n,k-1) $ [closed]

How to solve recurrence relations of the type $$a(n,k) = \frac{a(n-1,k-1) a(n,k-1)}{ a(n-1,k-1)}- a(n,k-1) $$ with $a(n,1) = n$? This was my main equation: which I have solved to reduce it ...
2
votes
1answer
22 views

Linear recurrence problem

Solve linear recurrence f(1) = 12, f(2) = 16, f(n) = 4f(n − 2). Hint: the solution has integer coefficients, so if you get square roots and/or difficult fractions, it’s likely that you have made a ...
0
votes
2answers
29 views

Solving Recurrence Relation with backwards substitution

I am calculating the effiency class of this R(n) = 2R(n−1)+2. with the base case of R(1) = 1 using backwards substitution. My equations came out to 4R(n-2) + 6 8R(n-3) + 14 16R(n-4) +30 I ...
0
votes
1answer
38 views

generating function from recurrence relation

I am referring to another question of mine: recurrence relation of a language However, in this question, I am considering the language X of bitstrings with no more than 3 consecutive zeros. (original ...
1
vote
2answers
60 views

Solving the recurrence relation $T(n)=4T(n-1)+n+1, T(0)=1$

I'm attempting to solve the recurrence relation $ T(n)=4T(n-1)+n+1, T(0)=1 $ From here I say $ T(n-1) = 4(4T(n-2)+n)+n+1 = 4^2T(n-2)+4n+n+1 $ $ = 4^2(4T(n-3)+n-1)+4n+n+1 = ...
2
votes
2answers
44 views

Solve the recurrence relation: $a_n = 6a_{n-1} - 9a_{n-2}$

Recurrence relation:$$a_n = 6a_{n-1} - 9a_{n-2}$$ Initial conditions:$$a_1 = 1, a_2 = 9$$ I am having a bit of trouble finishing off this problem. So far I have: Assume:$$a_n = r^n$$ $$r^n = ...
0
votes
1answer
33 views

How to solve this 2-D recurrence relation?

I am trying to solve this recurrence relation:- $$F(A,B)=\frac{F(A,B-1)F(A-1,B-1)}{F(A,B-1)-F(A-1,B-1)} ;\ F(A,1)=A$$ Please help in finding the general term of it.
6
votes
0answers
50 views

Asymptotic value of card drawing game

A deck consisting of $r_0$ red cards and $b_0$ black cards is randomly shuffled. The host turns up the cards one at a time; if it is red, you get $\$1$; otherwise you pay the host $\$1$ (and you're ...
0
votes
2answers
72 views

Solve the recurrence relations

Recurrence Relation: $$a_n = 6a_{n-1} - 9a_{n-2}$$ Initial Conditions: $$a_1 = -1, a_2 = 1$$ The answer in the back of the book is $$(2n-1)3^{n-1}$$ But I don't see how they got there. When using ...
0
votes
0answers
18 views

How can I solve a recurrence whose base case is not of size 1?

I am trying to solve the following recurrence function, but I am stuck since I don't think I can apply the Masters Theorem. B and M are predefined values (though not given), and $M>\Theta(B^2)$ ...
0
votes
1answer
22 views

Solving recurrence with big theta?

If f(n) = Ө n, what exactly is f(n)? This is what's throwing me off. I'm trying to solve using the master theorem. T(n) = 3T(n / 2) + Ө n
1
vote
2answers
41 views

closed form iterated logarithms

Is there any way that we could bound the following sum by a closed form expression $\sum_{i=1}^{\log^* N} \log^{(i)}N$ where $\log^{(i)}$ is the $\log$ function iterated $i$ time? Thanks
0
votes
2answers
33 views

About an non-autonomous difference equation

Let $r>4$ be a positive integer. Let us consider this difference equation: $$v_{n+1}-r^{2n+1}v_{n}=w$$ where $w$ is real number. How I can solve this equation with respect to $v_{n}$. I am not ...
2
votes
2answers
77 views

The amount of times a number need to be squared rooted

Consider the following recursive function $f()$ def f(x,n=0): if x<2: return n return f(math.sqrt(x),n+1) $f(x)$ calculates the number of ...
0
votes
1answer
70 views

Consider a recursive sequence. Find all values of x for which this sequence is bounded

Consider a recursive sequence $a_{n+1} = a_n + a_{n-1}$ for all $n \geq 2$ with $a_{1} = 1$ and $a_2 = x$. Find all values of $x$ for which this sequence is bounded.
0
votes
1answer
161 views

Climbing a n-stair staircase, taking 2 or 3 stairs each step…

Suppose a person has a n-stair staircase to climb, and they can go up exactly 2 or 3 stairs each time they take a step. Generate some initial data. Find and explain the recurrence relation to ...
1
vote
1answer
59 views

Binomial transform of Catalan numbers formula

How to prove that OEIS A007317 Binomial transform of Catalan numbers $a_{n}: 1, 2, 5, 15, 51, 188, 731, 2950, 12235, 51822, .. (n = 1, 2, ..)$ has a recurrence formula: $(n+2)a_{n+2} = (6n+4)a_{n+1} - ...
1
vote
1answer
53 views

I want to solve this difference equation: $H_{n+1}-(1+r^{2n+1})H_{n}=2-r^{2n+1}p_{n}$

Let $r>4$ be a positive integer. Let $p_{n}$ be the sequence of prime numbers with $n≥3$. I wante to solve this difference equation: $$H_{n+1}-(r^{2n+1}+1)H_{n}=2-r^{2n+1}p_{n}$$ where $H_{n}$ is ...
1
vote
1answer
161 views

Tile a 1 x n walkway with 4 different types of tiles…

Suppose you are trying to tile a 1 x n walkway with 4 different types of tiles: a red 1 x 1 tile, a blue 1 x 1 tile, a white 1 x 1 tile, and a black 2 x 1 tile a. Set up and explain a recurrence ...
0
votes
0answers
30 views

Chebyshev Polynomials of 1/n

The Chebyshev polynomials of the first kind are defined by the recurrence relation: $$ T_n(x) = 2xT_{n-1}(x) - T_{n-2}(x)$$ By using these polynomials, you can multiply the frequency of a cosine by ...
-1
votes
2answers
96 views

Does $\{x_n\}$ converge , $x_{n+1}=\frac{2}{3}x_n+ \frac{1}{x_n^2}$

Does $\{x_n\}$ converge where $$x_{n+1}=\frac{2}{3}x_n+ \frac{1}{x_n^2} \hspace{1cm} \forall n\in \Bbb{N}$$ and $x_1$ is close enough to $\sqrt[3]{3}$ So I noticed that if we could prove that ...
2
votes
1answer
71 views

Discrete mathematics puzzle

This is a question that i saw in one of the textbooks that i am doing exercise on and i am unable to solve it. I am not sure which method to use. Please help. Consider the following $n × n$ $(n ≥ 1)$ ...
4
votes
2answers
74 views

Limit of complex sequence.

I have the following limit: If $z_{n+1}=\dfrac{1}{2}\left(z_n+\dfrac{1}{z_n}\right)$ for $n \in \mathbb{N}\cup \{0\}$ and $-\dfrac{\pi}{2}<arg(z_0)<\dfrac{\pi}{2},$ then $$\lim_{n \rightarrow ...
2
votes
2answers
28 views

Given that $0<a<b$, $a_0=a$, and $b_0=b$, Show that $a_{n+1}=\sqrt{a_nb_n}$ is always increasing and $b_{n+1}=\frac12(a_n+b_n)$ is decreasing

This problem is very complicated and I feel like the answer should not require as much work as I am putting into it. Any tips/hints towards the solution are much appreciated!!
1
vote
2answers
48 views

Solving linear recurrences with repertoire method

$$\begin{align*} A_1 &= 0\\ A_{2n} &= 3A_n + n\\ A_{2n+1} &= 3A_n + n \end{align*}$$ I am trying to solve a recurrence of this form, after writing out small number I can see no pattern ...
0
votes
1answer
35 views

How to solve the following recurence relation [closed]

How to solve the following recurrence $T(n) = 1$, if $n=1$ $T(n) = 2T(n-1)+2T(n-2)+....+2T(1)$, if $n>1$ please help.
0
votes
0answers
20 views

Find the recurrence solution in an integral

$I_n=\int_{0}^{\frac\pi2} t^nsin(t), n\in\mathbb{N^*}$ I'm trying to find a general expression to compute this integral. I use integration by parts to find some $I_n$, and I can see some recursive ...
1
vote
1answer
28 views

How to solve the recurrence

How to solve the following recurrence relation? $T(n) = 1$ if $n=1$. $T(n) = T(n-1)+T(n-2)+T(n-3)+....+T(1)$ if $n > 1$. No clue about solving it. Help will be appreciated.
0
votes
1answer
24 views

Not understanding the recurrence formula of n nodes with a height h in an AVL tree to show $2 \log n \geq h$

I know the formula is: $n(h) = n(h-1) + n(h-2) + 1$ And I know it can be reduced as: \begin{align} n(h) & = n(h-1) + n(h-2) + 1 \\[6pt] & \geq n(h-2) + n(h-2) + 1 \\[6pt] & \geq 2n(h-2) ...
3
votes
4answers
95 views

How to find the limit of the sequence $x_n =\frac{1}{2}[x_{n-1}+x_{n-2}]$, if $x_0=0$ and $x_1=1$?

The formula is only applicable on values for $n\geq 2$. I know that the sequence is monotonic with a lower bound at $\frac 1 2$, but I am unsure how to find the supremum of the sequence. EDIT: $x_2 ...
2
votes
0answers
19 views

Boundary difference equation, monotonicity of the solution properties.

let's say we have a function $f \in C^{\infty}[a,b]$ such that $f,f',f'' > 0 \forall x \in [a,b]$ What i would like to prove is that the solution of this boundary problem $$\left\{ ...
3
votes
2answers
73 views

How to solve this nonlinear functional recurrence

I study two similar nonlinear functional recurrence systems, given by $$P_\pm:\qquad f_n\cdot(1\pm g f_{n-1}) = g\mp(1+2g)f_{n-1} \qquad (n>0)$$ and $$f_0=g$$ Here $f_n$ and $g$ are functions of ...
0
votes
0answers
18 views

Questions about this type of problem

Problem Consider the general chip-and-be-conquered recurrence relation: $T(n) = b_1T(n - 1) + b_2T(n - 2) + ... + b_kT(n - k) + f(n)$; for $n >= k$ for some constant $k >= 2$. The ...
1
vote
0answers
43 views

Prove that a polynomial of this form has a real root of this form.

Prove or disprove that for positive coefficients: $$a_k>0$$ this polynomial: $$a_1x^0+a_2x^1+a_3x^2+a_4x^3+...+a_nx^{n-1}-x^n=0$$ has a real root $x$ that is the fraction from the following ...
1
vote
0answers
58 views

Solving system of equations with summation

Is there a way to express $y_t$ in terms of $\delta$ and $p_t$ in the following system? $$ \begin{cases} & \sum\limits_{t=0}^{\infty}\delta^t\cfrac{p_t}{p_t+(1-p_t)y_t}=K \\ & ...
-3
votes
1answer
36 views

Help with recurrence relations question:

$$a_1=4$$ $$a_{n+1}=k(a_n+2)$$ $$\mbox{for}\ n\geq 1$$ How can I solve for $a_2$ if $$\sum\limits_{i=1}^3 a_i=2$$ You'll probably find it is really simple, but I've just started sequences and series ...
1
vote
1answer
30 views

Proving convergence of a sequence given by $a_{n+1}=A+Ba_n^3$

Given $A,B>0, A+B=1, 0<a_{1}\le A$ and a sequence $(a_n)$ with $a_{n+1}=A+Ba_n^3$. Determine with proof whether the sequence $(a_n)$ is convergent. I have tried a few values of $A,B$ and $a_1$, ...
0
votes
2answers
73 views

how can I prove it is a convergent sequence and how can I calculate its limit

Let we have the following sequence $$x_1=1$$ $$x_{n+1}=\frac{1}{2+x_n}$$ how can I prove it is a convergent sequence and how can I calculate its limit
1
vote
1answer
70 views

Evaluate the expression $\sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\cdots}}}$

Is there a way to check whether the expression below converges to a specific number. $$ \sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\cdots}}} $$ or in other words does the sequence defined by $x_0=\sqrt{2}$ and ...
1
vote
3answers
73 views

Solving the recurrence $a_n=2a_{n-1}-a_{n-2}$

How do I solve this recurrence relation? $a_n = 2a_{n-1} -a_{n-2} $, with initial conditions, $a_0 = 0 $ and $a_1 = 1$ I notice that this resembles Pell numbers, but have no experience in solving ...
0
votes
0answers
23 views

Types of solutions of a recurrence relations

I have studied about the general solution, particular solution and total solution. But I can't differentiate between them. Why we need three types of solution? Suppose we have a recurrence $a_n = ...
-2
votes
1answer
27 views

can't solve this recurrence, please help [closed]

Give a closed form for this: T(1) = 1 T(N) = T(n/2) + log(n) Anyone can show me how to solve this?
1
vote
2answers
53 views

Deriving an equation for the Sum of Alternating Combinations

Consider the equation $$A(n,m) = \sum_{i = 0}^m (-1)^i {n \choose i}$$ To get a feel for it, I let $n=5$ and $m \in \{1,2,...,5\}$ for $m=1$ $$A(5,1) = (-1)^0 {5 \choose 0} - {5 \choose 1} = 1 - 5 = ...
0
votes
1answer
55 views

Recurrence relation with series

I have the following recurrence relation to solve: $T(n) = 2\cdot T(n/4) + n^2$, $T(1) = 1$. This seemed pretty innocuous at first, after the first three steps, not so much. (1) given above (2) ...
1
vote
1answer
60 views

Derive the Differential Equation for Laguerre polynomials

How can i derive this linear differential equation $$ xD^2L^{(\alpha)}_n (x)+(1+\alpha -x)DL^{(\alpha)}_n (x)+nL^{(\alpha)}_n (x)=0 $$ from the following recurrence relations ...
1
vote
1answer
31 views

Solving a specific recurrence relation

I have no idea how to solve recurrence relations of the following kind (if they can even be solved), can anyone help me? This arose in my climate change class, it isn't homework but it would greatly ...