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

learn more… | top users | synonyms (2)

3
votes
2answers
291 views

A partial recurrence equation

What is the closed form solution to the following partial recurrence relation? $$ q(n,m) = \frac{q(n-1,m-1)}{n} - q(n-1,m) $$ where $q(0,m)=0$ for all $m > 0$ and $q(n,0) = (-1)^n$ for all $n \geq ...
3
votes
1answer
1k views

Need refresher on z-transforms and difference equations

I recently tried showing someone else how to solve a difference equation using z-transforms, but it's been a long time and what I was getting didn't look right. I was trying to solve the recurrence ...
3
votes
1answer
150 views

A difference equation related to RW on Hypercube

I am trying to solve the following recurrent relation $$ T(n)=\frac{n}{m}T(n-1)+\frac{m-n}{m}T(n+1)+1, \,\, \text{subject to } T(m)=0 $$ Where $0\leq n\leq m$ and $m$ is a fixed integer. I have ...
3
votes
1answer
73 views

Powers of $2 \times 2$ matrices expressed in linear form

I recently reopened an old high school math textbook and came upon the matrices unit. Some of the questions were those rewrite-in-linear-form problems: given, say, $M^2 = 2M - I$, express in linear ...
3
votes
3answers
202 views

The solution to the recurrence equation $T(n) = 2 T\left(\frac{n}{2}\right) + 2$

I got stuck at the solution to the recurrence equation $T(n) = 2 T\left(\frac{n}{2}\right) + 2$. Please give me a detailed explanation or references with detailed steps? Sorry, I missed something. ...
3
votes
2answers
441 views

Solution of $T(n)=2T(n/2) + n\log(\log n)$

I am struggling to solve this equation: $$T(n)=2T(n/2) + n\log(\log n).$$ I concluded that the Master Theorem does not apply in this situation so I tried to successively substitute the terms in order ...
3
votes
1answer
161 views

solving a recurrence

given the general recurrence equation $ a_{n+1}-a_{n}=f(n)a_{n+2}$ (1) is this possible to find a function $ g(x)$ so $ g(x)= \sum_{n=0}^{\infty}a_{n}x^{n}$ ?? where the $ a_{n}$ are the solutions of ...
3
votes
3answers
207 views

Recurrence relations problem (1st order, linear, constant coeff, inhomogeneous)

okay im supposed to find a recurrence relation for $$ a_{n+1}= b \cdot a_n + c \cdot n \ \ \ \ \ \ \ \ \ \ \ \ \mathbf{(1)} $$ where $b$ and $c$ are constants. the method we learned in class was ...
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: ...
3
votes
2answers
69 views

What are the polynomial solutions of the difference equation $W(x+h)=\frac{c(x+h)}{d(x+h)}W(x)$ for $W(x)$?

Let $d(x)=\prod_{s=1}^{n}(x-a_s)$ and $c(x)=\prod_{s=1}^{n}(x-a_s+b_s h)$ be polynomials, where $a_s, b_s$ are some complex numbers. What are the polynomial solutions of the difference equation ...
3
votes
1answer
92 views

Asymptotics of the solution of the following recurrence relation

$f(k)={k \choose k-1} f(k-1) + { k \choose k-2} f(k-2) + .... {k \choose 3} f(3)$ $f(3) = 1$ $k \ge 3$ Even good upper and lower bounds will help me as I am trying to find how this function grows ...
3
votes
2answers
56 views

Prove that largest root of $Q_k(x)$ is greater than that of $Q_j(x)$ for $k>j$.

Consider the recurrence relation: $P_0=1$ $P_1=x$ $P_n(x)=xP_{n-1}-P_{n-2}$; 1). What is closed form of $P_n$? 2). Let $k,j.\in\{1,2,...,n+1\}$ and $Q_k(x)=xP_{2n+1}-P_{k-1}.P_{2n+1-k}$. Then ...
3
votes
1answer
32 views

Decide if a stack of overhanging blocks is stable

Suppose I have overhand blocks $1,2,3$ up to $n$ units long, one of each kind. They are stacked over the table from smallest to largest so that their left edge alligns. Show if it is stable. ...
3
votes
2answers
51 views

How do I find $\liminf$ and $\limsup$ if $a_{2n}=\frac {a_{2n-1}}2$ and $a_{2n+1}=\frac12+\frac {a_{2n}}2$?

Its given that $a_1=a>0$ and that for any $n>1$ two things happen: $$a_{2n}=\frac {a_{2n-1}}2$$ $$a_{2n+1}=\frac12+\frac {a_{2n}}2$$ How do I find $\lim\inf$ and $\lim\sup$ I am trying to look ...
3
votes
1answer
116 views

How do I find an analytic solution to this recursive function?

I was playing with some recurrence relations, and I ended up with this a long nested function. How can I generalize the following relationship: $$ f_n = a + \frac{b}{f_{n-1}} $$ $$ f_1 = a + ...
3
votes
3answers
38 views

Solving Recurrence Relations using Iteration

$$a_0 = 2; \qquad a_k=4a_{k-1}+5 ~ \forall\ k\ge 1$$ I have already tried solving for $a_1$ through $a_5$.
3
votes
1answer
100 views

Derive a closed formula for the generating function of this recurrence relation

This is a given recurrence relation $a_n=19(F_0a_{n-1}+F_1a_{n-2}+...+F_{n-1}a_0)$ where $F_n$ is Fibonacci number and $a_0=9$. Find the generating function $A(x)$ of the sequence $a_n$ I get the ...
3
votes
1answer
135 views

Non-additive-subtractive prime sequence

Call the following a NON additive-subtractive prime sequence or lets name it Gary's sequence. It goes like this: let a(0)=2. The next term is defined as smallest prime number which cannot be expressed ...
3
votes
2answers
52 views

How does the recursion relation work in the solution to this differential equation (using series)?

Sorry for the vague title but it would not let me post the first step and last step of this equation (too many characters!). How does $$\dfrac{a_0}{3n(3n-1)(3n-3)(3n-4)\cdots 9 \cdot 8 \cdot 6 \cdot ...
3
votes
2answers
171 views

Solving a 2 independent variables (2nd degree) recurrence relation

Changes to the recurrences and definition are changed! See here: $f(n, 1) = 2n^2 $ and $f (n, k) = 0$ for $k \geq 2n$ and for $k < 0$ and $f(n, 2n-1) = 1$ for all $n$. Question: Is it possible ...
3
votes
2answers
49 views

Problem to understand a recurrence relation

In Norris, Markov chains, I found the following: [...] a recurrence relation of the form $$ ax_{n+1}+bx_n+cx_{n-1}=0 $$ where $a$ and $c$ were both non-zero. Let us try a solution of ...
3
votes
2answers
61 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 ...
3
votes
1answer
62 views

What's the time complexity of T(n)=nlogn+T(n-1)?

The title says it all. The best I can come up with is that this expands to T(0) + 1log 1 + 2log 2 + ... + (n-1)log (n - 1) + nlog n which is ...
3
votes
1answer
97 views

Help finding the closed formula for a recurrent relation

In the last steps of finding the complete solution of a linear differential equation by a power series, I got stuck on finding the closed formula for the following recurrent relation: $$B_n = B_{n-1} ...
3
votes
1answer
94 views

UNBEATABLE recurrence relation

Hi I don't know where to start to solve this reccurence relation: $g(1)=2$ $ g(2n)=3g(n)+1$ $ g(2n+1)=3g(n)-2$ of coures I can make it: $ g(1)=2$ $ g(n)=g(2n)/3-1/3$ $ ...
3
votes
1answer
993 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: ...
3
votes
1answer
196 views

Estimating linearly independent solutions to third order recurrence relation

I'm trying to prove something about two linearly independent solutions; $a_n$, $b_n$, to a recurrence relation I have - specifically that $\left| \frac{a_n}{b_n} \right|$ is eventually monotonically ...
3
votes
2answers
98 views

Is there a closed-form solution to this recurrence?

A friend and I were examining polynomials of the form $p_n (x) = x (x+1) (x+2) \cdots (x+n -1)$ and we were trying to come up with some kind of closed form for the coefficients when the polynomial is ...
3
votes
1answer
27 views

Analyzing $n_{i+1} = n_i - n_i^{3/4}$

I have a non-linear recurrence given by $$n_0 = N \\ n_{i+1} = n_i - n_i^{3/4}$$ Are there any techniques to solve this for an exact closed form? Or in lieu of that, an asymptotic estimation? I'm ...
3
votes
1answer
67 views

Equivalent of a recurrence sequence [duplicate]

Let $x_{0} = 2$ and $x_{n+1} = x_{n} + \ln(x_{n})$, how can I find an asymptotic equivalent of this sequence say, to the third term? (This is not homework, it was a problem in the Oral Examination ...
3
votes
2answers
70 views

Does $E^2 \; ( E \approx 1.2640847\ldots)$ equal $D \approx 1.5979102\ldots$?

Does $E^2=D$? Where $E$ is a constant used in the closed form of the Sylvester Sequence (see: Closed form formula and asymptotics) and $D$ is a constant for the closed formula of the sequence A007018 ...
3
votes
1answer
227 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 ...
3
votes
1answer
251 views

Minimum period of function such that $f\left(x+\frac{13}{42}\right)+f(x)=f\left(x+\frac{1}{6}\right)+f\left(x+\frac{1}{7}\right) $

Let $ f$ be a function from the set of real numbers $ \mathbb{R}$ into itself such for all $ x \in \mathbb{R},$ we have $ |f(x)| \leq 1,f(x)\neq constant $ and ...
3
votes
1answer
134 views

Proof for recursively defined sets

Language $L\subset \{a,b\}^*$ is such that: $\epsilon \in L$ $a \in L$ For any $x\in L$, $xb\in L$ and $xba\in L$ Nothing else in $L$. Im just learning recursive sets, but with that definition am ...
3
votes
1answer
85 views

A Generalized Fibonacci sequence

I have the following recurrence $$u_{n+1}=u_{n}+a^{N-n}u_{n-1}\quad n\ge 1$$ where $$N\ge 1,\quad u_1=u_0=1,\quad 0< a\le 1$$ I want to find out $u_N$. My Try: For $a=1$ this is just the Fibonacci ...
3
votes
1answer
123 views

What does $x_n = s\, x_{n-1}$ mean in the components of recurrence?

Say you have a reucrrence $x_{n+1} = 3x_n+2$. Though, it is a inhomogenous, it can be represented by a linear system $$\begin{bmatrix} x_{n+1}\\1\end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 0 & ...
3
votes
2answers
216 views

Purchasing Order: An Analysis on A ($\textrm{C++}$)-Approached Recurrence Relation

Suppose that we have $n$ dollars and that each day we buy either tape at a dollar, paper at a dollar, pens at two dollars, pencils at two dollars, or binders at three dollars. If $R_n$ is the number ...
3
votes
1answer
209 views

Meaning of a zero in an eigenvector for the solution of a system of difference equations

In a system of first order difference equations, I get the following solution $\begin{bmatrix} x_{1,t} \\ x_{2,t}\end{bmatrix} = \begin{bmatrix} \mathcal{A} \\ 1 \end{bmatrix} \lambda_1^t + ...
3
votes
1answer
260 views

Diagonalizing/eigenvalues of a particular infinite dimensional matrix

I have trying to show that the continuum limit of n quantum harmonic oscillators gives rise the the Klein-Gordon field. However, instead of a usual finite string, I want to do it on a ring. Assume $n ...
3
votes
1answer
585 views

Using a definite integral, to create a specific recurrence relation.

Hello i have the integral: $$y_n=\int_0^1\frac{x^n}{x+5}dx$$ where $ n=1,2,3,4,....,\infty$ I need to show that the integral can be represented by the recurrence relation below; $$y_n= ...
3
votes
4answers
233 views

Proving that $T(n) = 3T\left(\frac n3\right) + \sqrt n = \Theta(n)$

Show that $T(n)$ is bounded both above and below by $n$ (abusing the Big O notation) for some positive constants $c_1$ and $c_2$: $$ T(n) = 3T\left(\frac n3\right) + \sqrt n = \Theta(n) $$ ...
3
votes
1answer
724 views

Derive Bell number recurrence by considering equivalence classes

I have the following question: Let $q_0 = 1$ and, for $n \geq 1$, let $q_n$ denote the number of equivalence relations on a set $X$ with $n$ elements. By considering the possible equivalence ...
3
votes
2answers
112 views

Solve recurrence formula

Thanks! That helps a lot. I think the substituting is the way to go
3
votes
3answers
256 views

When is a linear recurrence relation solvable?

I was reading this definition of a linear recurrence, and was wondering what characteristics are required of a linear recurrence for it to be solvable? Meaning, can I find a closed form? The subject ...
3
votes
2answers
112 views

The k-th difference of the sequence $n^{k}$ is constant and equal to $k!$

Define the k-th difference of a sequence $\{a_n\}$ inductively as follows: The $1$-th difference is the sequence $\{b_n\}$ given by $b_n=a_{n+1}-a_n$ The "$k+1$"-th difference is the sequence ...
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, ...
3
votes
1answer
713 views

Solving a recurrence relation using back substitution.

This is related to analysis of algorithms (divide and conquer), but since it's mostly math, I thought it would be better to post here instead. I'm trying to solve a recurrence relation using back ...
3
votes
1answer
4k views

Recurrences that cannot be solved by the master theorem

I am given this problem as extra credit in my class: Propose TWO example recurrences that CANNOT be solved by the Master Theorem. Note that your examples must follow the shape that $T(n) = ...
3
votes
1answer
839 views

Binary Strings of the form *111* [duplicate]

Possible Duplicate: Counting subsets containing three consecutive elements (previously Summation over large values of nCr) Given an integer $N$, we have to count the number of possible ...
3
votes
2answers
658 views

Particular solution of recurrence equations

How do we solve recurrence equations of the form: $$ax_{n+1}+bx_n+cx_{n-1}=dn^p+e\;,$$ where $a,b,c,d,e$ are constants and $p\in \mathbb Z$? Perhaps we could first solve the homogeneous equation ...