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

learn more… | top users | synonyms (2)

2
votes
1answer
57 views

Find and solve a recurrence relation for the number of n-digit ternary sequences in which no 1 appears to the right of any 2.

Find and solve a recurrence relation for the number of n-digit ternary sequences in which no 1 appears to the right of any 2. $a_1=3$ and $a_2=8$ I am having trouble creating the recurrence relation ...
2
votes
2answers
64 views

Recurrence Relation from Old Exam

I see this challenging recurrence relation that has a solution of $T^2(n)=\theta (n^2)$. anyone could solve it for me? how get it? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 ...
2
votes
5answers
29 views

Solve recursion with constant added

I have the following problem: Define a sequence $(a_n)$ where $a_1 = 4$ and $a_n = 4a_{n-1} - 4$. Find a closed form for $a_n$. So basically I usually know how to deal with recursions like $a_n = ...
2
votes
1answer
33 views

Recurrence relation of the following sequence?

This is the code: for (unsigned int i = 0; i < n; ++i) if (i % 2 == 0) ++k; And this is the output for when ...
2
votes
2answers
51 views

Help with a recurrence relation

I have been battling with the following: $$T\left(n\right)=3T\left(\frac{n}{2}\right)+n\log(n)$$ I have tried expanding it but the term $n\log(n)$ gets very messy. What is the approach for solving ...
2
votes
1answer
72 views

Solving recurrence relation

If I have the following recurrence relation, $$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + n $$ How would I show that $T(n)\le cn\lg(n)+dn $ for some reals $c$ and $d$?
2
votes
2answers
74 views

The growth of the solution of the recursive relation $P(n)=\sum_{k=1}^{n-1} P(k) P(n-k)$

According to my notes,one solution of the recursive relation: $$P(n)=\sum_{k=1}^{n-1} P(k) P(n-k), \text{ for } n>1 \\ P(1)=1$$ is $\Omega(2^n) $. How do we conclude that this is one solution?
2
votes
2answers
95 views

Calculate f(n+1)-f(n-1) based on f(n)???

Being: $$f(n) = \left(\frac{5+3\sqrt5}{10}\right)\cdot\left(\frac{1+\sqrt5}{2}\right)^n+\left(\frac{5-3\sqrt5}{10}\right)\cdot\left(\frac{1-\sqrt5}{2}\right)^n$$ Calculate: $$f(n+1)-f(n-1)\\ ...
2
votes
1answer
39 views

Solving recurrence

Can anyone help me solving this recurrence? I don't see how I could use Master Theorem for this one and I couldn't find anything that would give me some idea how to do this. $$ T(n) = ...
2
votes
3answers
38 views

Recursive integration

The integral I have is $$I_{n} = \int^{\pi/2}_{0} \cos^{2n+1}y \ \mathrm{d}y$$ And I have found $I_{n} = \frac{2n}{1+2n}I_{n-1}$ but I want to express $I_{n}$ in a form without $I_{n-1}$ how do I do ...
2
votes
1answer
80 views

Solving a (non-linear?) recurrence relation in 2 variables

I'm not sure if this problem is linear or not. Anyway, let me state the problem first: $$ \begin{align} P_n(a) &= \left(1 - \frac{a}{n} \times \frac{a-1}{n-1}\right) \times P_{n-1}(a) + ...
2
votes
2answers
109 views

Recurrence relation practice problem that I can't figure out

Thanks for taking the time to look at this problem. I'm trying to prepare for a test on Monday by doing some extra odd numbered problems from my textbook. I'm having a lot of trouble trying to solve ...
2
votes
2answers
50 views

Determining Values

I have tried a couple of ways to get started / finish this problem but I cant seem to figure out how to fully explain and determine the value of $x_n$. I have posted my question below with figures to ...
2
votes
3answers
121 views

Proof that $x^2 - 2y^2 = -1$ has a recurring solution for $x$

I read here about the following variation on Pell's equation: $$ x^2 - 2y^2 = -1.$$ According to Dario Alpern's solver, the equation has infinite integer ...
2
votes
1answer
109 views

If $ x_{1} := 1 $ and $ x_{n + 1} := x_{n} + \dfrac{n}{(x_{1} \times \cdots \times x_{n})^{1/n}} $, then $ \dfrac{x_{n}}{\ln(n)} \to \infty $.

Define a sequence $ (x_{n})_{n \in \mathbb{N}} $ of positive real numbers by $$ x_{1} := 1 \quad \text{and} \quad \forall n \in \mathbb{N}: \quad x_{n + 1} := x_{n} + \frac{n}{(x_{1} \times \cdots ...
2
votes
1answer
67 views

Where can I find information on “Quadratic Maps”?

According to Wolfram, a quadratic recurrence relation uses a second degree polynomial to express $x_{n+1}$ as a function of $x_n$. A "quadratic map", then, is a recurrence relation: $$x_{n+1} = a ...
2
votes
2answers
306 views

Solve the following non-homogeneous recurrence relation:

Find the solution to the following non-homogenous recurrence relation: $a_{n+2} - 4a_{n+1} + 4a_{n} = 2^n$ for $a_0=1, a_1 = 2$. I have found from the characteristic polynomial the general homogenous ...
2
votes
1answer
383 views

Number of ways to partition a set with $n$ elements to $k$ subsets where at least one subset has $r$ elements

I'm familiar with Stirling numbers of the second kind to compute the number of ways to partition a set with $n$ elements into $k$ non-empty, disjoint subsets. However, there are combinations which I ...
2
votes
1answer
38 views

Difference equation: $y_{k+1} = y_{k} + \frac{c}{2k}$

I'd like to solve this difference equation. Unfortunately, the forcing term is not geometric, so I don't know how to find the solution: $$ y_{k+1} = y_k + \frac{c}{2k}. $$
2
votes
1answer
147 views

How to find a recurrence relation for the following sequence

I have to find a recurrence relation that generates the sum of the first $n$ cubes, that is $s_n = 1 + 8 + 27 + \dots + n^3$ considering that $n=1,2,3,\dots$ I also have to find a recurrence relation ...
2
votes
4answers
913 views

How to find a closed form solution to a recurrence of the following form?

I need to find the closed form solution to the following recurrence -: $ T(n) = 8*T(n/2) + 0.25*n^2$ with $T(1) = 1$ and $n=2^j$ and this is what I have tried so far but just can't seem to get a ...
2
votes
1answer
46 views

Question about fixpoints and zero's on the complex plane.

Define property $A$ for an entire function $f(z)$ as $1)$ $f(z)=0$ has exactly one solution being $z=0$ $2)$ $f(z)=z$ has exactly one solution $=>z=0$ (follows from $1)$ ) $3)$ $f(z)$ is not a ...
2
votes
2answers
86 views

A Recurrence Equation From a Game

$a_n=a_{n-1}(a_{n}-a_{n-2}+1)$ The above equation is defined in $[0,m]$ st. $a_{0}=0$ and $a_m=1$. It turned up as I was trying to analyze a simple richman game. I have managed to solve the equation ...
2
votes
2answers
240 views

recurrence relation homework question

This is a homework question let $a_n$ number of n digit quaternary $(0,1,2,3)$ sequences in which there is never a$ 0 $anywhere to the right of a $3$. Solve for $a_n$ bot sure how to go about this. ...
2
votes
1answer
285 views

Recurrence relation for $n$ numbers in which no 3 consecutive digits are the same.

I am stuck on trying to find (and solve) a recurrence relation to find all n-digit numbers in which no 3 consecutive digits are the same. These numbers are in decimal expansion. Now I first ...
2
votes
2answers
120 views

How do I solve the following recurrence?

Solve the recurrence $$X_n =\begin{cases} n & 0 \leq n < m\\ X_{n-m} + 1 & n \geq m.\end{cases}$$ So I've started with several base cases, but since the answer depends on $n$'s ...
2
votes
1answer
63 views

How to evaluate $\lim_{n \to \infty}{\frac{a_1 \cdot a_2\cdot a_3 \ldots a_{n}}{a_{n+1}}}$, given $a_{n+1} = a_{n}^{2} -1,a_1 = \sqrt{5}$?

Let $a_{n+1} = a_{n}^{2} -1,a_1 = \sqrt{5}.$ How would one evaluate $$\lim_{n \to \infty}{\frac{a_1 \cdot a_2\cdot a_3 \ldots a_{n}}{a_{n+1}}}?$$ Added: Someone else asked me this question today, ...
2
votes
1answer
127 views

Recurrence Relation with Square Root

Well, I was doing a problem on recurrence relation , where there was given a an recurrence relation and we had to find $a_{n}$ or simplify the recurrence. The recurrence relation was $$\begin{align} ...
2
votes
1answer
46 views

Finding a linear recurrence regarding strings

The question is Let $T(n)$ be the number of length-$n$ strings of letters $a$, $b$ and $c$, that do not contain three consecutive $a$'s. Give a recurrence relation for $T(n)$ and justify it. (You do ...
2
votes
2answers
447 views

Recurrence Relation for Strassen

I'm trying to solve the following recurrence relation (Strassen's):- $$ T(n) =\begin{cases} 7T(n/2) + 18n^2 & \text{if } n > 2\\ 1 & \text{if } n \leq 2 \end{cases} ...
2
votes
3answers
101 views

Solution to Recurrence Relation

I asked a question previously, about how to describe $$ f(n) = n^3 $$ As a recurrence relation. I was, quite rightly, given $a_1=1$ and $a_{n+1}=a_n+3n^2+3n+1$. I have attempted to solve it, using ...
2
votes
2answers
85 views

Expressing a sequence as a recurrence relation

I've been working on a project, and it's come to that time when I have to prove the run time complexity of an algorithm. I've obtained my metric and those things that have nothing to do with you guys! ...
2
votes
2answers
129 views

Tricks to Solve Arbitrary Recursions

Consider two recursions: (1) $a_{n+2} = 2a_{n+1} - a_n + 4n3^n$ with $a_0 = a_1 = 1$ (2) $na_n = (n-2)a_{n-1} + n/2$ with $a_0 = 0$ When I look at the first recursion it suggests to me that I ...
2
votes
2answers
257 views

How do you find the closed form of these recurrence relations?

I found these two recurrence relations in an old textbook and was hoping someone could show me how to solve them for their closed form. If not, a final answer would also be appreciated, as it helps ...
2
votes
1answer
167 views

Solving for the closed form of a recurrence relation

Can someone concisely explain how we can find the closed form of a recurrence relation? I know the iterative process is generally the preferred method, but I'm having trouble deriving the steps and ...
2
votes
2answers
88 views

Help solving summation series of a recursive function

Yesterday in class, we were analyzing the Karatsuba multiplication algorithm and how it applies to recurrence equations. Time ran short, and I feel I missed how to solve the final summation. First, ...
2
votes
2answers
333 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 ...
2
votes
2answers
242 views

Question about theta of $T(n)=4T(n/5)+n$

I have this recurrence relation $T(n)=4T(\frac{n}{5})+n$ with the base case $T(x)=1$ when $x\leq5$. I want to solve it and find it's $\theta$. I think i have solved it correctly but I can't get the ...
2
votes
2answers
56 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 ...
2
votes
1answer
822 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}$ ...
2
votes
1answer
132 views

Difficult partial solution to a reccurence equation

I am trying to help a friend of mine solve $$ a_n + 5 a_{n-1} + 6 a_{n-2} = 12n - 2(-1)^n$$ Now the homogenous solution is easy to find, and one just needs to solve the equation $r^2 + 5r + 6 = 0$ ...
2
votes
2answers
402 views

How to solve this recurrence relation $T(n) = T(n/5) + T(4n/5) + O(1)$

Given the recurrence: $$T(n) = T(n/5) + T(4n/5) + O(1)$$ The annoying part is $O(1)$. If it were some $g(n)$, then I could use recursion tree on $n$, but there is no such $n$ to start with. So I ...
2
votes
1answer
250 views

Finding Probability Generating function for $P\left\{ X > n+1\right\} $

I am trying to find probability generating function for $P\left\{ X > n+1\right\} $. Let X be a random variable assuming the values $0, 1, 2, ...$. The notation both for the distribution of $X$ ...
2
votes
2answers
88 views

What's $T\left(n\right)$?

If $T\left( n \right) = 8T\left( n-1 \right) - 15T\left( n-2 \right); T\left(1\right) = 1; T\left( 2 \right) = 4$, What's $T\left(n\right)$ ? I use this method: Let $c(T(n) - aT(n-1)) = T(n-1) - ...
2
votes
2answers
195 views

Recurrence equation for central trinomial coefficients

I've come across the following exercise: Give a recurrence equation for the central coefficients $(a_n)$, where for all $n$, $a_n$ is the coefficient of $X^n$ in $(1+X+X^2)^n$. Here's what I've ...
2
votes
3answers
2k views

Recurrence equation $T(n)=3T(\sqrt{n}) +1$

I need to find an exact solution to the following recurrence using substitution (change of variables). $$ T(n) = 3T(\sqrt{n}) + 1, \quad \text{ when } n > 2, $$ and $$ T(2) = 1 .$$ I can't get ...
2
votes
3answers
132 views

Problem with generating functions and binary recurrences

I am considering the following recurrence: $a_0 = 1$; $a_1 = 2$ $a_{n} = 2 (a_{n - 1} + a_{n - 2})$ Then I proceeded with the generating function: $F(x) = \displaystyle\sum_{n = 0}^\infty a_n x^n ...
2
votes
1answer
76 views

Want to show that $T(n)\leq dn^2$

On page 9 (70) in http://russell.lums.edu.pk/~cs211aw07/slides/clrs-rec.pdf they try to argue that $T(n) \leq d n^2$ using the substitution method. Someone who can explain in details why $cn^2$ in ...
2
votes
1answer
489 views

Correspondence between ODE and difference equation

In Wikipedia about difference equations, there is some description about correspondence between ODE and difference equation: If you consider the Taylor series of the solution to a linear ...
2
votes
2answers
258 views

Solve recursion $p[n,m] = p[n-1,m-1] + p[n+1,m-1] + p[n,m-1]$

How to solve the recursion: $$p[n,m] = p[n-1,m-1] + p[n+1,m-1] + p[n,m-1]$$ Ideally in general, but if you need base cases: $$p[n,0] = 0 \text{ (for } n \neq 0),$$ $$p[0,0] = 1$$ I've asked a ...