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

learn more… | top users | synonyms (2)

0
votes
0answers
13 views

Difference equation of Z-Transform

I could not obtain difference equation of Z-Transform which is indicated below: $$H(z) = \frac {1.1202\cdot10^{-6}z^2 + 2.2404\cdot10^{-6}z + 1.1202\cdot 10^{-6}}{z^2 -1.9996z + 0.996}$$ In simple ...
14
votes
4answers
892 views

How does one solve this recurrence relation? [closed]

We have the following recursive system: $$ \begin{cases} & a_{n+1}=-2a_n -4b_n\\ & b_{n+1}=4a_n +6b_n\\ & a_0=1, b_0=0 \end{cases} $$ and the 2005 mid-exam wants me to calculate answer ...
0
votes
2answers
29 views

Proving a sequence defined by a recurrence relation converges

How can I prove that this iterative sequence converges to $2$? Can I use the convergence definition? $$a_{n+1} = \frac{a_n}{2} + \frac{2}{a_n},\qquad a_0 = 4 $$ Thanks for the help.
0
votes
2answers
16 views

Finding a general form $d_n$ for a recurrence relation

I have the following recurrence relation $$d_n = 2^{(1-2n)/2}d_{n-1},\qquad d_0=1,$$ for $n\in\mathbb{Z}$. Is it possible to find a general form for $n$? After calculating a few numbers around ...
0
votes
0answers
22 views

best way to find sum of powers of prime factors of a number

What is the best way to find the sum of powers of prime factors of a number? What I did till now is : ...
0
votes
2answers
48 views

Solution to recurrence relation, as a formula involving summation operator

Here is what I am tasked with.. Find a solution to the recurrence relation: $F(0) = 2$ $F(n+1) = F(n) + 2n^2 - 1$ as a formula involving the summation operator $$\sum_{i=1}^n$$ Sorry for the ...
0
votes
1answer
38 views

Solving the recurrence $ T[n] = \frac{n}{T[n-1]}$

Ive had some experience solving recurrences but i think they have been more simple than this one. This is what i have so far: \begin{array}{rcl}T[1] & = & 1 \\ T[n] & = & ...
1
vote
2answers
15 views

Alternative Derivation of Recurrence Relation for Bessel Functions of the First Kind

How can the recurrence relation $J^{'}_n(x) = \frac{1}{2} [J_{n-1}(x) - J_{n+1}(x)]$ be derived directly from the following? $J_n(x) = \frac{1}{\pi} \int_0^\pi \cos(n\theta - x \sin\theta) \text{d} ...
-2
votes
1answer
27 views

Periodicity of solutions of rational difference equations $x_{n+1}=\alpha+\frac{x_{n-1}}{x_n}$ [closed]

\begin{equation*}x_{n+1}=\alpha+\frac{x_{n-1}}{x_n}\tag{1}\end{equation*} Equation(1) has solutions of prime period 2 if and only if $\alpha = 1$. How to prove this? Thanks.
0
votes
0answers
23 views

Solving a recurrence relation using a subtitution method $T(n+1)=T(\frac {n} {2} )+ \Theta\left(n^2 \right) $

I got stuck when I want to solve this recursive relations by substitution $$ T(n+1)=T(\frac {n} {2} )+ \Theta\left(n^2 \right) . $$ $$ T(n+1)=2 T(\frac {n} {2} )+ \Theta\left(n\right) . $$ $$ ...
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 ...
2
votes
1answer
25 views

unfolding of a recurrence

I've been reading the book "Concrete Mathematics" from Graham et. al. And there is a relation (on pg. 27) $s_n = s_{n-1}a_{n-1}/b_n$, and authors point that this relation can be unfolded, resulting ...
2
votes
1answer
27 views

How to rearrange this doubly infinite sum for a diffeomorphism using the existence of a first integral?

Let's take two diffeomorphisms $F,G: \mathbb{R}^{n} \mapsto \mathbb{R}^{n}$. Let $x \in \mathbb{R}^{n}$, and $x^{n} = F^{n}(x)$, where $n \in \mathbb{Z}$. Suppose that $F$ has a first integral, i.e. ...
6
votes
5answers
170 views

Convergence of a recurrence

Given the recursive definition (starting with a positive integer) $$ a_n = \frac{a_{n-1}}{2}+4 $$ I am trying to find an explicit form and show that it approaches 8. So I started by writing it out, ...
0
votes
1answer
15 views

How to solve the recurrence relation

I was going through a problem on combinatorics and came up with the recurrence relation like this. These equations hold for all natural values of $n$. ($p_n$ is the final result that I want) ...
28
votes
2answers
391 views

Find $\sqrt{4+\sqrt[3]{4+\sqrt[4]{4+\sqrt[5]{4+…}}}}$

Find the value of $$\sqrt{4+\sqrt[3]{4+\sqrt[4]{4+\sqrt[5]{4+...}}}}$$ I know how to solve when all surds are of the same order, but what if they are different? Technically, (as some users ...
0
votes
0answers
25 views

Finding a shorter recursive equation

The assignment is the following: (a) Given a sequence $(a_n)_n$ which satisfies the recursive equation $a_n = \sum\limits_{k = 1}^d c_k \cdot a_{n-k}$ with $c_d \not= 0$. Furthermore $Q = 1 - c_1t - ...
0
votes
0answers
24 views

How to solve this recurrence relation with a summation in it?

How would one go about solving this recurrence relation: $T(n)$=$\sum_{i=1}^{k}T(n - d_i)$ ? For this recurrence relation, $k$ is the number of coin denominations, and $d_i$ is the specific coin ...
-2
votes
1answer
31 views

Prove recursive relation by induction [closed]

Let say i have the following relation - $$T(1) = c1$$ $$T(n) = T(n/2) + n$$ I need to prove by induction that this function is bounded by $O(n)$. I just dont get how to choose $C,N_{0} > 0$ . If ...
0
votes
0answers
24 views

what will be closed form of $P_vP_{2n-v-1}-P_{v-1}P_{2n-v}?$

Let $$P_0=1,$$ $$P_1=x,$$ $$P_n(x)=xP_{n-1}-P_{n-2}.$$ For some $v∈\{1,2,…,n+1\} $, what will be closed form of $$P_vP_{2n-v-1}-P_{v-1}P_{2n-v}?$$ I want a close form like ...
-1
votes
1answer
40 views

General formula for harmonic sequence

Arithmetic sequence and arithmetic mean are correlated like that $$ a_n=\frac{a_{n-1}+a_{n+1}}{2} $$ So all elements of arithmetic sequence $a_n=a+(n-1)r$ are satisfy that. $$ ...
3
votes
3answers
43 views

Is regular selection from recurrence also recurrence?

Let $R$ be a ring, and $u=(u(0),u(1),u(2),...)$ be a sequence over $R$ ($u(i)\in R$). Let $m\ge1$, $c_0,...,c_{m-1}\in R$ be fixed elements, and the following law of recursion holds ...
0
votes
2answers
223 views

Solving the Recurrence Relation/Series fn = 1 + fn-1*(M) where M is a constant

So I'm trying to solve this week's FiveThirtyEight Riddler. In a building’s lobby, some number (N) of people get on an elevator that goes to some number (M) of floors. There may be more people ...
0
votes
1answer
33 views

Use strong induction to prove that $f_n = g_n$ for all $n \in \mathbb{N}$.

I would like to use strong induction to prove that $f_n = g_n \; \forall n \in \mathbb{N}$, where $f_n$ is defined as: $f_0 = 1 \\ f_1 = 5 \\ f_2 = 10 \\ f_n = 2f_{n-1} - 4f_{n-2} \; \text{for $n ...
0
votes
0answers
17 views

Recurrence relation by substitution method

I have to find the lower and the upper bound for the following recurrence: $T(n)=\sqrt{n} T(\sqrt{n})+\sqrt{n}$ and use the substitution method. I have trouble finding out how the recursion-tree ...
0
votes
2answers
24 views

what is the value of K for given recurrence relation?

Consider the recurrence relation $a_1 = 8$, and for all $n>1$, $a_n=6n^2 + 2n+a_{n–1}$. Let $a_{99} = K\times 10000$. The value of $K$ is ___.
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
81 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} ...
0
votes
1answer
38 views

Given the recurrence $T_n = 2T_{n-1} - T_{n-2}$, prove by Induction that $T_n = n$

Given the recurrence$$T_n = 2T_{n-1}-T_{n-2},$$$$T_0=0$$$$T_1=1$$Prove by induction, that $T_n = n$. I have the first few steps worked out. Basis: $n = 1$$$T_1=1=n=1$$ Assume true for $n = ...
0
votes
2answers
35 views

Find the sequence defined by the recurrence equation $x_{n+1} = 4x_n − x_{n−1}, (n ≥ 1)$

Find the sequence defined by the recurrence equation $x_{n+1} = 4x_n − x_{n−1}, (n ≥ 1)$ with $x_0 = 1$ and $x_1=2$. Find an odd prime factor of $x_{2015}$. I've found the characteristic equation to ...
1
vote
3answers
43 views

Find a close form expression for $f(x)$

Here is the problem I am currently having trouble with. I have a pretty decent basis on how to do recurrence relations, but the $\frac{1}{n!}$ has got me in a rut. I tried multiplying the right side ...
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) = ...
0
votes
2answers
50 views

Find and solve a recurrence relation for the number of words of length n from letters A, B, C, and D

Find and solve a recurrence relation for the number of words of length $n$ from letters $A, B, C,$ and $D$ which contain at least one $A$ and the first $A$ comes before the first $B$ (if there are any ...
0
votes
2answers
19 views

How to calculate three constants in a linear recurrence problem.

Question: Verify that $x^3 - 3x^2 + 4 = (x^2 - 4x + 4)(x+1)$ And solve linear recurrence: $f(0) = 1$, $f(1) = 0$, $f(2) = 14$, $f(n) = 3 f(n-1)- 4 f(n-3)$ The characteristic equation is already ...
0
votes
0answers
6 views

Time complexity for recursion

For, this recursion, What's the time complexity? T(n) = 3T(n/2) + O(log n) I think I can't use the master's theorem because a = 3, b = 2 then log2(3) = 1.58 and f(n) = n^0*log(n), so c = 0 and it ...
2
votes
1answer
41 views

solve $a_n=5a_{n-1}-4a_{n-2}+3\cdot2^n$ with initial conditions $a_0=1, a_1=10$

so i am pretty sure that i have solve the homogeneous solution correctly. $a_n^h = B\cdot 4^n+C\cdot1^n$ however I am not so confident on the particular solution. Here was my attempt. Since ...
0
votes
0answers
13 views

Recurrence relation without master's theorem

$$T(n) = T(n/2) + O(n \log n).$$ I don't think I can use master's theorem because $a = 1$, $b = 1$ then $\log b a$ is $log_2(1) = 0$. And $f(n) = n\log(n)$, so $c = 1$. Then $c \ne 0$. So second form ...
0
votes
0answers
9 views

Explicit solution for a non-linear recurrence equation

Does the following non-linear recurrence equation has an explicit solution with given boundary conditions $x_0$ and $x_\infty$? $$ x_n = a + b x_{n-1}x_{n+1} $$ $a$ and $b$ are constants.
0
votes
4answers
62 views

Trying to solve recurrence $T(n)=3T(n/3) + 3$

I'm trying to solve the following recurrence without using the Master Theorem: $$T(1)=1;$$ $$T(n)=3T(n/3) + 3$$ My attempt: $T(n) = 3T(n/3) + 3$ $ = 3(3T(n/9) n/3)) + 3)$ $ = 9T(n/9) + 9$ $ = ...
2
votes
0answers
16 views

Find Theta Class of T(n) = T(3n/4) + T(n/6) +5n [duplicate]

I'm not quite sure I can apply the Master Theorem to T(n) = T(3n/4) + T(n/6) + 5n. It is not in the normal form of T(n) = aT(n/b) + f(n). Is it possible to apply the MT to it? If not, can the ...
0
votes
0answers
36 views

Multivariable recurrence: Solving $c(n,k) = c(n-1,k) + c(n-1,k-1) = \binom{n}{k}$ by algebraic methods.

Let $(c_{n,k})_{n,k=0}^{\infty}$ be defined by $c(0,0)=1$, $\:\:c(0,k)=0 \:\: \forall \: k > 0$ $$c(n,k) = c(n-1,k) + c(n-1,k-1) \:\:\: \forall \: n \geq 1$$ I can show that the ...
0
votes
0answers
31 views

Finding “equilibrium”

Say I have three amounts $A$, $B$ and $C$. And a set of conversions between them $K_{A->B}$, $K_{B->A}$ and $K_{B->C}$. The conversions denote what fraction and at what efficiency they ...
0
votes
0answers
34 views

upper bound on derivatives of a function defined on an arc

Given a smooth arc on the complex plane by $z=\cos t + 0.5 i \sin t,\; t\in[\pi/10,\pi/5] $ , and a non-analytic function $f(z) = \text{Re } z $ defined on the arc. Obviously, $f(z) = g(t) ...
1
vote
1answer
32 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 ...
0
votes
0answers
24 views

Proving running time with induction

I need to use induction to prove the run time of the given recurrences: $T(1) = c_1$ $T(n) = T(n-1) + c_2$ Well this is the first time Im doing induction on this kind of exercise - I would like ...
0
votes
0answers
17 views

Can you identify this stochastic process?

So I run into this problem the other day and I cannot even think of the keywords I need to use to look it up. For the discrete random variable $X$ we have: $P_{\Delta X(t)} = F\big(X(t-1), ...
0
votes
4answers
67 views

Power series solution (Why the constant of the recurrence relation can be chosen arbitrarily?)

Please help me understand this: Solve $(x+1)y''-(2-x)y'+y =0$ First, since $x_0=0$ is an ordinary point, it can be guaranteed that we can find two independent power series solutions centered at ...
0
votes
1answer
18 views

Proving Recurrence Relation By Forward Substitution

I'm having trouble understanding the inductive proof of the following recurrence relation by forward substitution. I get that were plugging in the value for our induction step into the relation but I ...
0
votes
1answer
65 views

Solving a series of equations

I'm writing a piece of code to translate some data, and I keep banging my head against the wall with a one part of the transformation. I'm not as good at math as I ought to be :) Say we have a ...
0
votes
0answers
7 views

How to solve a difference equation with an input?

How do you solve the difference equation (initial conditions are given) $$y(k)+ay(k-1)+by(k-2)=cx(k-1)+dx(k-2)$$ where the input $x(k)=\theta(k)$ (the unit step function). I know that the general ...