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

learn more… | top users | synonyms (2)

3
votes
1answer
356 views

Solving recurrence equation with floor and ceil functions

I have a recurrence equation that would be very easy to solve (without ceil and floor functions) but I can't solve them exactly including floor and ceil. \begin{align} k (1) &= 0\\ k(n) &= n-...
3
votes
2answers
155 views

How is Ramanujan's recurrence relation for his nested radical solved?

The Wikipedia article, here, describes in some detail the derivation of Ramanujan's famous nested radical, $$\sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{1+\cdots}}}}.$$ In the Wikipedia article it provides a ...
3
votes
1answer
46 views

Find recursive formula for special function

Kind of a strange question I know, but here goes: We are given a string of letters $T$ without any gaps or commas, just letters. Depending on what $T$ is, it could be broken down to form a valid ...
3
votes
1answer
45 views

Solving recurrence relation with repeating roots

I am aiming to solve this recurrence relation and I have chosen the Characteristic Equation method: $d_n = 4(d_{n-1}-d_{n-2})$ with $d_0 =1, d_1=1 $ Finding the C.E. I get: $x^2-4x+4=0$ Solving for ...
3
votes
3answers
73 views

Examine the convergence of a sequence $\{a_{n}\}$ which is given by $a_{1}=a>0,a_{2}=b>0, a_{n+2}=\sqrt{a_{n+1}a_{n}},n\ge 1$

I used inequality between arithmetic and geometric means to show that a sequence $\{a_{n}\}$ is bounded: $$a_{n+2}=\sqrt{a_{n+1}a_{n}}\le \frac{a_{n+1}+a_{n}}{2}$$ Solving this, I get quadratic ...
3
votes
2answers
127 views

How do I solve the recurrence relation without manually counting?

Given the recurrence relation : $a_{n+1} - a_n = 2n + 3$ , how would I solve this? I have attempted this question, but I did not get the answer given in the answer key. First I found the general ...
3
votes
2answers
86 views

What is wrong with my solution for the recurrence $T(n)=2T(\sqrt{n})+\lg\lg n$?

an someone explain where did I do a mistake? Solve the recurrence relation $$T(n)=2T(\sqrt{n})+\lg\lg n$$ Let$$\lg n = m$$ $$S(m) = 2S(m/2)+\lg m$$ We know (proved in class) that $$S(m) = O(m \lg m)$$...
3
votes
1answer
160 views

Recurrence relation of number of groups of matching parenthesis

I was trying to solve this problem: How many ways can N pairs of parenthesis form K matching groups? By 'a group of matching parenthesis' I mean a sequence of matching parenthesis which can not be ...
3
votes
2answers
222 views

“Multiplication” of two linear recurrence relations

Array $a_n$ is defined as: $$a_0 = 1, \quad a_{n+1} = k_{a1}a_{n} + k_{a0}$$ Array $b_n$ is defined as: $$b_0 = 1, \quad b_{n+1} = k_{b1}b_{n} + k_{b0}$$ Array $c_n$ is defined as: $$c_n = a_{n}...
3
votes
4answers
77 views

General Solution for a non-Homogeneous Recurrence

What is the general solution to the recurrence: $$x(n + 2) = x(n + 1) + x(n) + n - 1$$ where $n\geq 1$ with $x(1) = 0, x(2) = 1$? It's a question on a practice exam I'm reviewing and I'm not ...
3
votes
1answer
281 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, ...
3
votes
3answers
97 views

Solve the recurrence relation $a_n=3a_{n-1}+n^2-3$, with $a_0=1$.

Solve the recurrence relation $a_n=3a_{n-1}+n^2-3$, with $a_0=1$. My solutions: the homogeneous portion is $a_n=c3^n$, and the inhomogeneous portion is $a^*_n=-1/2n^2-3/4n+9/8$. This results in a ...
3
votes
1answer
158 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 ...
3
votes
2answers
84 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 }\...
3
votes
5answers
42 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 = a_{...
3
votes
2answers
247 views

MNTILE SPOJ Tiling patterns

We have tiles of size 2 * 1. We need to arrange the tiles to get the floor size of m * n. For ...
3
votes
1answer
154 views

General Solution of Functional Equation

What is the general solution to: $$ \frac{f(x+h)-f(x)}{h} = \frac{1}{x} \tag{1} $$ Obviously the solution to this for the limiting case of $h\to 0$ is $f(x) = \ln(x) + c$ Attempting to solve the ...
3
votes
2answers
192 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 ...
3
votes
2answers
136 views

recursion-consecutive numbers

what is the number of subsets of the set {k∈N|1≤k≤n} with no two consecutive numbers? The answer says: $$a_n=a_{n-1}+a_{n-2}$$ with the starting conditions: $$a_0=1, a_1=2$$1. why does $a_1=2$? $$$$ 2....
3
votes
3answers
115 views

Recurrence $f(a,b)=f(a,b-1)+2f(a-1,b-1)$

Consider the recurrence relation $$f(a,b)=f(a,b-1)+2f(a-1,b-1)$$ for integers $a,b\geq 2$, where $f(a,b)=1$ if $a=1$ or $b=1$. Is it possible to find a closed form for $f(a,b)$?
3
votes
2answers
445 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. ...
3
votes
2answers
65 views

Soving Recurrence Relation

I have this relation $u_{n+1}=\frac{1}{3}u_{n} + 4$ and I need to express the general term $u_{n}$ in terms of $n$ and $u_{0}$. With partial sums I found this relation $u_{n}=\frac{1}{3^n}u_{0} + ...
3
votes
2answers
99 views

Strong Mathematical Induction: Prove $3\mid b_n$ for a given recurrence relation $b_n$

Here is what I have so far: Proof $3\mid b_n$ for $n$ integers $\geq 1$ Base Cases both given $b_1=3, b_2=9$ and $b_n=6b_{n-2}+b_{n-1}$ $$P(1)=3\mid b_1$$ $$P(1)= 3\mid 3$$ Since $3\mid 3$, the ...
3
votes
2answers
176 views

Given $g(x)$, how to solve function recurrence $f(x)=af(\alpha x)+bf(\beta x)+g(x)$ where $\alpha\neq\beta$

If we have a recurrence like $$f(x)=af(\alpha x)+bf(\beta x)+g(x)$$ where $a,b,\alpha,\beta\in\mathbb{R}$ and $\alpha\neq\beta$ and $g(x)$ is known. How can we solve this kind of recurrence? For ...
3
votes
2answers
154 views

How to solve the differential equation $u_k(z)=-2\cfrac{\partial}{\partial z }(\cfrac{u_{k+1}(z)}{z})$?

$$e^{z\sqrt{1-t}}=\sum \limits_{k=0}^\infty \frac{u_k(z)t^k}{k!}$$ $$\frac{\partial}{\partial t }(e^{z\sqrt{1-t}})=\frac{\partial}{\partial t }(\sum \limits_{k=0}^\infty \frac{u_k(z)t^k}{k!})$$ $$\...
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
74 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
206 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
442 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: $n^{log_b{...
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 $W(x+h)...
3
votes
1answer
93 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
33 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
74 views

A recursively defined sequence and a limit

Fix real numbers $ a_0 $, $ a_1 $ and define, $$ a_{n+1} = a_n + \Big(\frac{2}{n+1} \Big) a_{n-1} \space \space \forall \space n \ge 1 $$ Show that the sequence $ \Big\{ \dfrac{a_n}{n^2} \Big\}_{n=1}^...
3
votes
1answer
123 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 + \frac{...
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
105 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
136 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
50 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$ $ g(n)=g(2n+1)/3-2/...
3
votes
1answer
1k 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: $a_{k}...