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

learn more… | top users | synonyms (2)

2
votes
2answers
84 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
128 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
254 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
161 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
87 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
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 ...
2
votes
2answers
233 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
55 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
780 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
130 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
390 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
248 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
192 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
129 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
484 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 ...
2
votes
1answer
28 views

How to prove that nth differences of a sequence of nth powers would be a sequence of n!

Given an infinite sequence of numbers, first differences denote a sequence of numbers that are pairwise differences, second differences denote a new sequence of pairwise differences of this sequence, ...
2
votes
3answers
25 views

Limit of a difference equation

Given $y_{k+1} = 1 + \sqrt{y_k}$ for $k \geq 0$ and $y_0 = 0$, we have a limit of the form $L = \lim_{k \rightarrow \infty} y_k = 1 + \sqrt{1 + \sqrt{1 + \sqrt{1 + ... \sqrt{1 + \sqrt{2}}}}}$. ...
2
votes
3answers
44 views

Finding recurrence relation for strings of length n formed from A, B, C?

Let $S_n$ be the number of strings of length $n$ formed from letters A, B, C, that do not contain substrings AB, BA, AAA or BBB. For example, for $n = 3$, all strings with this property are: AAC, ...
2
votes
1answer
79 views

Prove the summation involving Stirling numbers of the first kind

I have been trying to prove or disprove this for 2 days now, but i don't even know where to begin. $$ 1 = \sum_{m=1}^{n} \sum_{k=1}^{n} \frac{x^{n-m}(-1)^{n-k-m} \left[\matrix ...
2
votes
1answer
41 views

How do you prove uniqueness of solution of homogeneous linear recurrences?

I was following the MIT 6.042 course on OCW (that don't cover generating function on the lectures, sorry if the answer is easier by doing that method). Recall a linear homogeneous recurrences is of ...
2
votes
1answer
40 views

Solving recurrence -varying coefficient

How can one find a closed form for the following recurrence? $$r_n=a\cdot r_{n-1}+b\cdot (n-1)\cdot r_{n-2}\tag 1$$ (where $a,b,A_0,A_1$ are constants and $r_0=A_0,r_1=A_1$) If the $(n-1)$ was not ...
2
votes
3answers
53 views

How to derive the closed form of this recurrence?

For the recurrence, $T(n) = 3T(n-1)-2$, where $T(0)= 5$, I found the closed form to be $4\cdot 3^n +1$(with help of Wolfram Alpha). Now I am trying to figure it out for myself. So far, I have worked ...
2
votes
1answer
33 views

Find all sequences that satisfy the recurrence relation

Find all sequences that satisfy the recurrence relation $$u_n\cdot (u_{n+1})^2-u_{n+1}-u_n+1=0, \text{with }u_0=1$$ My try First, we find $u_1$, which follows $u_0=1$. $u_0\cdot ...
2
votes
1answer
59 views

How prove there exist postive integer $n$ such $x_{n}>y_{n}$

let two positive sequence $\begin{cases} x_{n+2}=x_{n}+x^2_{n+1}\\ y_{n+2}=y^2_{n}+y_{n+1} \end{cases}$ and $x_{1}>1,y_{1}>1,x_{2}>1,y_{2}>1$ show that: there exists $n$, such ...
2
votes
2answers
42 views

Solving a Recursive equation, wrong options? [closed]

This is a very simple recursive formula. Are the options provided wrong? $$ T(n) = T\left(\frac{n}2\right) + 2 $$ with $T(1) = 1$. What's the solution when $n=2^k$ ($n$ is a power of $2$)? The ...
2
votes
2answers
79 views

Finding a Closed Form for a Recurrence Relation

I know that a general technique for finding a closed formula for a recurrence relation would be to set them as coefficients of a power series (i.e. a generating function). Then use properties of ...
2
votes
2answers
34 views

Find general solution

I want to find the general solution for the following : $$t(n)=t(\frac{n}{4})+\sqrt{n}+n^2+n^2log_{8}n $$ Note: $n=4^k$ $t(n)=t(4^k)=t_{k}$ $$t_{k}=t_{k-1}+2^k+16^k\cdot \frac{2}{3}k$$ ...
2
votes
2answers
35 views

Solving divide and conquer recurrence

I have a recurrence $T(n)$ with only powers of two being valid as values for $n$. $$T(1) = 1$$ $$T(n) = n^2 + \frac{n}{2} - 1 + T(\frac{n}{2})$$ I tried to substitute $n=2^m$, which yields the ...
2
votes
1answer
40 views

How can I find a recursive relation for the following words?

if c(n) is the number of words created by the alphabet {a,b,c} with n length that the word does not contain 'ab' term then write a recursive relation for c(n). I don't have enough knowledge of the ...
2
votes
2answers
42 views

Find suitable recurrence relation

So I need to find a correct recurrence relation to this problem: How many series of size n over {0,1,2} exist, so that each digit never appears alone. For example, this series is good: 000110022, and ...
2
votes
1answer
37 views

Solving a recurrence realtion using forward substitution.

I have to find $T(n) = 7 \cdot T\left(\frac{n}{7} \right)$ for $n>1$ when $n$ a power of $7$. So far I have: $$T(7) = 7\cdot T\left(\frac{7}{7}\right) = 7 \cdot T(1) = 7.$$ Then, $$T(49) = 49 ...
2
votes
1answer
254 views

Guess an explicit formula for recursively defined sequence

Was given this as a question. "Use iteration to guess an explicit formula for the recursively defined sequence and then prove that the formula is a solution to the recurrence using induction: ...
2
votes
3answers
141 views

How to Find Recurrence Relation?

I'd appreciate help in understanding how to approach/find a recurrence relation. For example, if we are given the following situation, how would one find a recurrence relation? A computer system ...
2
votes
1answer
84 views

Define a recursive sequence for the following formula f(n) = n(n+1)

Define a recursive sequence for the following formula f(n) = n(n+1). Preferably one only defined by previous $a_n$ terms, i.e., no 'n' terms. If possible that is. So for example the following ...
2
votes
2answers
106 views

Internet problem solving contest question

I am trying to solve a problem from the IPSC http://ipsc.ksp.sk/2001/real/problems/f.html It basically asks to compute the following recursion. ...
2
votes
5answers
70 views

stuck trying to solve nonhomogeneous recurrence relation

hello and happy new year! I'm trying to solve this question: We are required to find the solution (direct formula) of the following recurrence relation: $b(n)=b(n-1)+n-1$, $b(0)=0$. What I did: I ...
2
votes
2answers
91 views

proof with recurrence relation

How can we proof that number ternary strings that do not contain two consecutive 0s or 1s is $a_n = 2a_{n-1} + a_{n-2}$ What I tried so far: Let $a_n$ be the number ternary strings that do not ...
2
votes
1answer
32 views

Find a direct way to calculate recursive elements (simple problem with matrices)

I nearly solved this question, I just need a hand with the last part since it is a bit confusing. We are given the recursive sequences $\{a_n\}$ and $\{b_n\}$ like this: $a_1=1$, $b_1=2$ ...
2
votes
2answers
58 views

Solving non homogenous recurrence relation

Find all solutions of the recurrence relation $$a_n = 2a_{n-1}+ 3^n$$ The $3^n$ is really throwing me off.
2
votes
2answers
79 views

Combinatorics arrangement on chessboard

How many ways we can fill $n\times n$ chessboard (with any number of pawns) so that out of every two pawns, one of them was to the left and and down from the second? My ideas: I think that this task ...
2
votes
2answers
194 views

Limit of a fraction of double factorials

How can we show that $\begin{align*} \lim_{n\rightarrow\infty} U_n = 0 \end{align*}$ where $\begin{align*} U_n = \frac{(n-1)!!}{n!!}=\frac{n-1}{n}\frac{n-3}{n-2}\frac{n-5}{n-4}\cdots \end{align*}$ ...
2
votes
1answer
127 views

number of derangements

In the normal derangement problem we have to count the number of derangement when each counter has just one correct house,what if some counters have shared houses. A derangement of n numbers is a ...
2
votes
2answers
57 views

Recurrence Relations and Characteristic Equations

I am not understanding how to go from the beginning of a recurrence relation to the end. I do not understand how to get to the characteristic equation. I can factor it if I know where it comes from. ...
2
votes
1answer
74 views

Recurrence relation of an integral [closed]

$$ y_n = \int_0^1 \frac{x^n}{x+5} dx,\ \ n=0,1,2,...,\infty $$ What is the recurrence relation between $y_n, y_{n-1}$ ? Could you provide me a methodology on how to proceed with this?
2
votes
1answer
370 views

How to find recurrence relation of a given solution.

Determine values of the constants $A$ and $B$ such that $a_n=An+B$ is a solution of the recurrence relation $a_n=2a_{n-1}+n+5$. I know that the characteristic equation is $r-2 = 0$ which has the root ...
2
votes
1answer
94 views

Recurrence Relation.

I was searching the internet when I came a across a question, and just couldn't solve it. I kept rearranging and substituting but kept going around in loops. "For $n:= 1,2,3,.....,$ Let $$ I_n = ...