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

learn more… | top users | synonyms (2)

1
vote
1answer
84 views

Recurrence Equation with Polynomial Coefficients

As inspired by this question on the problem site Brilliant, Let $F_n(a,b,c)=a(b-c)^n+b(c-a)^n+c(a-b)^n$ Is it possible to obtain $F_n$ in terms of $F_3, F_2$? My attempt at a solution is as ...
1
vote
1answer
65 views

Recursive sequence.

Given $a_0=0$, $\displaystyle a_n=\frac{3a_{n-1}+1+\sqrt{12a_{n-1}+1}}{3}$, find $a_n$ in terms of $n$. By finding the first few terms of $a$, I get a pattern and deduce that $a_n=n(n+1)/3$. I ...
1
vote
1answer
466 views

Program, Recurrence relation, Master-Theorem

Programming code: t(n) { for i=1 to n sum=sum+1 if (n>1) sum=sum+t(n/2)+t(n/2) return sum } I built the ...
1
vote
2answers
142 views

Solving a recurrence relation

I have a recurrence relation that I would like to solve. $T(n)$ belongs to $\Theta(f(n))$. $T(n) = 2T(\frac{n}{4}) + c$, where $c$ is a constant. The base case, $T(1)$ is a constant as well. My ...
1
vote
3answers
170 views

How to solve two recurrences dependent on each other

Let $F_n = a_1*F_{n-1} + b_1*F_{n-2} + c_1*G_{n-3}$ $G_n = a_2*G_{n-1} + b_2*G_{n-2} + c_2*F_{n-3}$ We are given $ a_1,b_1,c_1,a_2,b_2,c_2$ and $ F_0,F_1,F_2, G_0, G_1,G_2 $. We have to calculate ...
1
vote
2answers
36 views

Solving a recurrence based on the solution to another.

I have a solution to a recurrence $g(n)=f(n) + g(n-1)$, and I'd like to solve the recurrence $h(n) = \alpha[f(n) + h(n-1)]$. I guessed the solution was $h(n) = \alpha^ng(n)$, but it turns out this ...
1
vote
1answer
77 views

Explicit formula for recurrence relation with $A_{N+1}= A_N+{(2/7)}^N$

How can I find a non-recursive formula for the sequence $A_N$ when the sequence is defined as $A_1=1$ and for $N\ge 1$, $A_{N+1}= A_N+{(2/7)}^N$?
1
vote
2answers
98 views

Guidelines for Obtaining Recursive Equations?

I'm trying to teach myself some combinatorics, and at the moment, I'm having a hard time coming up with recursive equations. It seems to come naturally to some people, and I'm hoping that my skills ...
1
vote
1answer
90 views

Find a closed form for the recurrence relation $h_{n}=h_{n-1}+(n-1)+\sum_{k=1}^{n-1} {n-2 \choose k-1}h_{k-1}$

I have a recurrence equation as follows: $$h_{n}=h_{n-1}+(n-1)+\sum_{k=1}^{n-1} {n-2 \choose k-1}h_{k-1}\;,$$ with $h_{0}=0,h_{1}=1,h_{2}=2$.
1
vote
2answers
629 views

How to find the order of a recurrence relation

I have some homework that I'm working on where there is a whole section of problems I need to solve taking the following form: "Assume that T(1) = 1, and find the order of function T(n)." I have no ...
1
vote
3answers
303 views

How to solve this recurrence problem?

problem: Find the recurrence relation satisfied by $R_n$ , where $R_n$ is the number of regions that a plane is divided into by $n$ lines , such that There are $k$ lines among $n$ lines that are ...
1
vote
1answer
1k views

How to find recurrence relation for this problem?

How to find a recurrence relation for F(n) the number of ways to make n cents change using only pennies, nickels(5cents), and dimes(10cents)... So for 9 cents, there are 6 ways, which are ...
1
vote
2answers
444 views

How to come up with a recurrence relation?

In general what are some things you can do to come up with a recurrence relation for something? I've had it covered in a course in combinatorics that I took, but our professor would always say "you ...
1
vote
1answer
352 views

Recursive solution to a Diophantine equation

I'd like to find a recursive formula giving positive integer solutions to this Diophantine equation $$5L^2 - a^2 - 1 =0$$ It can be seen that I need $5L^2 - 1$ to be a square of a number $\in \mathbb ...
1
vote
1answer
49 views

How to choose substitution to make the difference equation linear with fixed coefficients?

I am going over some lecture notes and there is the following exercise: Solve $$(k+1)^{2}y(k+1)-k^{2}y(k)=1$$ with the initial condition $$y(1)=0$$ where $k$ it for the time, hence not ...
1
vote
1answer
1k views

Recursion relation for the number of ternary string that does not contain two consecutive characters.

Ternary strings are those that contain only 3 characters at most. For ex: abcbca is ternary string over set {a,b,c}, etc. Can anyone tell what will be the recursion relation for the string that does ...
1
vote
2answers
1k views

Proving convergence of a recurcive sequence $a_{n+1}=\ln(a_{n}+2)$.

Suppose we have a sequence defined by $a_{n+1}=\ln(a_{n}+2)$. We want to prove that for every $a_{0}>0$, the sequence converges to the same $g\in\mathbb{R}$. This is where I got so far: Let's ...
1
vote
2answers
5k views

$T(n) = 2T(n/2) + n \log n$ recurrence relation using master theorem

Assume that $$T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n \log n)$$ By Generic form of master theorem with $a = 2$, $b = 2$ and $f(n) = c \, n \log n$, it can easily be proved that $T(n) = ...
1
vote
3answers
528 views

Recurrence substitution method

I just want to see if I did this right. I need to show that $T(n) = 3T(n/4) + n\log n$ shows that $T(n) = O(n\log n)$ using substitution method in recurrence. $$T(n) = 3c(n/4 \log n/4) + n\log n$$ ...
1
vote
2answers
429 views

Fibonacci Sequence Variants

I learnt about finding the $n$th Fibonacci number using matrix exponentiation in $\log n$ time. Then I tried finding similar formula for sequences of the form $$S_{n} = S_{n-1} + S_{n-2} + a n + b$$ ...
1
vote
1answer
1k views

Ulam's problem - guessing a chosen number in a set

I tried to solve the following problem, which I found in the book "Discrete Mathematics and Its Applications", by Kenneth Rosen (Problem 28 of the section 7.3 of the 6th Edition): Suppose someone ...
1
vote
1answer
1k views

Visualize a difference equation with Matlab [closed]

I have a difference equation for a Single Pole Infinite Impulse Response Filter, defined on a discrete time-series: $y[n]-(1-\alpha)*y[n-1]=\alpha*x_n$ While the []s brackets refer to a position n ...
1
vote
1answer
164 views

Simple recurrence relation in three dimensions

I have the following recurrence relation: $$f[i,j,k] = f[i-1,j,k] + f[i,j-1,k] + f[i,j,k-1],\quad \mbox{for } i \geq j+k,$$ starting with $f[0,0,0]=1$, for $i$, $j$, and $k$ non-negative. Is there ...
1
vote
1answer
3k views

Give a recursive definition for the set of polynomials with integer coefficients.

I'm thinking of the form $$p_n = a_0t^0 + a_1t^1 + a_2t^2 +\cdots + a_nt^n.$$ However the only way I can think to write it is $$p_n = p_{n-1}+ a_nt^n.$$ I'm probably thinking the wrong way. This ...
1
vote
1answer
86 views

number of ways to form a specific number with n digits

I'm trying to find the number of ways to form a number with certain properties. The number has following properties. The first digit is always 1. The $n$th digit can take values from 1 to k+1 ...
1
vote
1answer
138 views

“Non-commutative” Recurrence relation $ C_m = \alpha_m C_{m-1} + \beta_m C_{m-2} $

I have a problem, which is probably quite trivial. Consider a recurrence relation of the form $$ C_m = \alpha_m C_{m-1} + \beta_m C_{m-2}, $$ where the coefficients $\alpha_m$ and $\beta_m$ are ...
1
vote
1answer
368 views

Solve non-homogeneous recurrence relation

I'm stuck on a recurrence relation that arises in a simulation I'm writing. Does anybody know how to proceed on this? I'm not even sure, because of the variable coefficient, how to get the associated ...
1
vote
1answer
298 views

Matrix recurrence equation

We define a $"2 \times 2"$matrix $A$. The following recurrence equation is given:$$A^{k+1}=\frac{A^k}{k}+I,(k=1,N)$$where $I$ is the identity matrix. How can I find the matrix $A$? Thanks
1
vote
2answers
1k views

prove a monotonically increasing function from recurrence relation by induction

How to prove $T(n)$ is a monotonically increasing function by induction provided that $T(n) = T(n/2 + \sqrt{n}) + \sqrt{6046}$? $n$ is larger than $n/2 + \sqrt{n}$ when $ n \geq 5$ and it is ...
1
vote
2answers
5k views

$T(n)=3T(n/2) + n\log n,\ T(1)=1$ [duplicate]

Possible Duplicate: $T(n) = 4T({n/2}) + \theta(n\log{n})$ using Master Theorem What is the order of this recurrence? $$T(n)=3T(n/2) + n\log n,\ \ T(1)=1$$ I found the answer where ...
1
vote
1answer
220 views

Recursive algorithm substitution?

I'm working through a problem set through MIT's OpenCourseWare and am having some trouble with recurrences. The problem is 1-2d: Give asymptotic upper and lower bounds for $T(n)$ in each of the ...
1
vote
1answer
70 views

Prove that $x_{n} = (n^{2}(n+1)^{2})/4$ via complete induction for the sequence $x_{n+1}=x_{n} + (n+1)^3$

The sequence is described by $x_{n+1}=x_{n} + (n+1)^3$. Prove that $x_{n} = (n^{2}(n+1)^{2})/4$ via complete induction. I actually have two questions. I'm a bit lost as to how to start the induction ...
1
vote
1answer
698 views

Recurrence Relation, closed-form (linear, 2nd order, constant coeff, homogeneous)

If I have a recurrence relation, such as $h_n = h_{n-1} + 2h_{n-2}$, is there a rigid method to find a closed formula for $h_n$? As of right now, I just solve for the first few terms $h_0, h_1, h_2, ...
1
vote
2answers
474 views

Simple Maths Question - Capital Sigma/Pi

I haven't studied math in a long time and am trying to solve a simple first order non-homogeneous recurrence relation. This approach uses the general formula: $$ f(n) = \prod_{i=a+1}^n b(i) \bigg\{ ...
1
vote
1answer
27 views

Where does this reccurence relation come from?

if$$\alpha_m = \int^{1}_{-1}\cos \pi x (x^2-1)^m dx$$ then how do I get $$\alpha_m = \frac{-1}{\pi^2}(2m(2m-1)\alpha_{m-1} + 4m(m-1)\alpha_{m-2})$$ I have to integrate by parts! But $$\alpha_n = ...
1
vote
1answer
76 views

Given $x_m=4x_{m-1}-x_{m-2},\ x_1=1,\ x_2=3$

I friend told me that apart from trivial ones, the elements in this sequence never equal powers of 3: $$x_m=4x_{m-1}-x_{m-2},\ x_1=1,\ x_2=3.$$ Could you please help me to prove this?
1
vote
1answer
44 views

Master theorem with $f(n) = n\log(\log n)$

I have a question related to algorithm time complexity and master theorem. How to solve this master theorem $T(n) = 2T(n/2) + n\cdot \log(\log(n))$? We have 3 cases: I don't know which one to ...
1
vote
1answer
26 views

Solution to a 2D recurrence equation

I am seeking an explicit solution to this 2D recurrence equation: \begin{eqnarray} f(0,b) & = & b\\ f(a,0) & = & a\\ f(a,b) & = & f(a-1,b) - f(a,b-1) \end{eqnarray} So, for ...
1
vote
2answers
28 views

Solve the recurrence $a_n=3a_{n/3}+2$ given $a_0=1$ and $n$ is a power of $3$

Solve the recurrence $$a_n=3a_{n/3}+2$$ given $a_0=1$ and $n$ is a power of $3$ I am trying to study for my final using my previous quizzes, of which I got this question wrong. My instructor wants me ...
1
vote
1answer
82 views

limit of $a_n$ when n to infinity. $a_1=\sqrt{k}$ and $a_n = \sqrt{k}^{a_{n-1}}$ . $0<k<1$.

I find a question on quora: limit of a sequence. Generalized Case 1 When you generalize this question like: \begin{align} a_1 &= \sqrt{k} \\ a_n &= \sqrt{k}^{a_{n-1}} \end{align} ...
1
vote
2answers
43 views

Find the generating function for the recurrence $a_n=a_{n-1}-a_{n-2}$, with $a_0=0$ and $a_1=1.$

This was a test question and I felt confident about it but all he put on it was no and circled a problem and left it at that. My solution up until I messed up which was early was $G_a(x) = ...
1
vote
1answer
33 views

Series with recursive terms: reciprocal of the sums of previous terms

What are some references and material that are devoted to studying series of the form $x_1+\frac1{x_1}+\frac{1}{x_1+\frac1{x_1}}+\dotsc$ where $x_1>0$ is given? For instance, my (non math) friend ...
1
vote
1answer
67 views

A sum of Stirling numbers of the second kind

Find a formula (either exact or asymptotic in $N$) for $S(N)$, where \begin{equation} S(N) = \sum_{n=N}^\infty \sum_{k=N}^n \sum_{j=0}^k \binom{k}{j} (-1)^{k-j} (1+j)^n \frac{t^n}{n!}. \end{equation} ...
1
vote
1answer
31 views

Help resolving particular solution to recurrence relation?

$a_n=5a_{n-1} - 6_{n-2} + 4^n + 2n + 3$ for $n>=2$ , $a0 = 5, a1 = 19.$ I get the general solution $ c_n = C_12^n+C_23^n.$ For a particular solution in the form $pn = An + B + C4^n$; we have ...
1
vote
1answer
19 views

Prove that $\displaystyle\int_{x=-1}^{1}P_L(x)P_{L-1}\acute (x)\,\mathrm{d}x=\int_{x=-1}^{1}P_L\acute(x)P_{L+1} (x)\,\mathrm{d}x=0$

A question (Problem $7.4$) in my textbook (Mathematical Methods in the Physical Sciences - 3rd Edition by Mary L. Boas P578) asks me to Use $$\int_{x=-1}^{1}(P_L(x)\cdot\text{any polynomial of ...
1
vote
1answer
32 views

Closed formula for finite product series

I need to solve the recurrence: $$ \begin{align*} T(n) &= kT\left(\frac{n}{2}\right) + (k - 2)n^3 \\ &\textit{where}\; k \in \mathbb{Z}: k \geq 2 \\ &= ...
1
vote
5answers
70 views

recurrence relation unable to solve

I am trying to solve recurrence relation : $$z_n = 2z_{n-1} + z_{n-2} \;\;\;\;\;z_0=1\;\;\;z_1=3$$ Could you please help to provide a solution. I got stuck with Lamdas.. Are there some simple ...
1
vote
1answer
29 views
1
vote
1answer
42 views

Relation between two sequences or summations

Let us define two sequences \begin{equation} G_{n}=\sum_{i=1}^n a^{-i}t_{i-1} \end{equation} and \begin{equation} g_{n}=\sum_{i=1}^n t_{i-1} \end{equation} where $a$ is an integer and $t_n$ is an ...
1
vote
1answer
31 views

Limit of $13^{a_n}=12^{a_{n-1}}+5^{a_{n-2}}$

I have the following recurrence: $$13^{a_n}=12^{a_{n-1}}+5^{a_{n-2}},\;a_0=0,\;a_1=1.$$ I have to prove that it is monotone and bounded, and I have to find the limit as $n\to\infty$. It was for an ...