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

learn more… | top users | synonyms (2)

0
votes
0answers
4 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 ...
1
vote
0answers
23 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
10 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
7 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
58 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
28 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
29 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
22 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
30 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
19 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
61 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
15 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
64 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
6 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 ...
1
vote
1answer
61 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} ...
0
votes
1answer
15 views

First-order Taylor series expansion

I have a first-order equation that is supposed to be solved using the Frobenius method. I am having some difficulty since the equation is not equal to zero. I would appreciate any help. y' + (1 - ...
0
votes
1answer
10 views

Find a recurrence relation for a retirement account with an initial deposit of $1000 and 3% interest per year

Given that the 3% interest per year is compounded monthly and that the person saving up adds $200 to the account each month: If for each integer ($n$) greater than 0, $A_n$ is the amount the account ...
1
vote
1answer
47 views

Solving a Recurrence Relationship

Given recurrence relationship: $g(1) = 5;\\ g(2n) = 4g(n);\\ g(2n+1) = 4g(n).$ I feel lost because of $g(2n)$ and $g(2n+1)$. Based on my coursebook, there is the common standard form, which can be ...
0
votes
1answer
28 views

Recurrence Relation; unusual exercise (For me at least)

I'm having some trouble with this reccurence problem. Usually we have just one term like $2^n$ or $3n$, but this time there one of each kind. $$\begin{align} a_{n}=5a_{n-1} - 6a_{n-2} + 2^n + 3n ...
0
votes
1answer
41 views

Solve $T(n)=16T(n/2)+2n^4$

Solve using the iteration method: $$T(n)=16T(n/2)+2n^4$$ My attempt: $$\begin{align} T(n) &=16\cdot16T(n/2^2)+2(n/2)^4+2n^4 \\ &=16\cdot16\cdot 16T(n/2^3)+2(n/2^2)+2(n/2)^4+2n^4\\ ...
0
votes
0answers
13 views

Solving recurrence relations question? [duplicate]

Hey I dont know how to do this question. Can any pls show me the working out for these question. Questions: http://pasteboard.co/uSZZRst.jpg
0
votes
1answer
16 views

Is it possible to solve a recurrence with max()?

I have the following problem. Imagine there is a set $P=\{p_1,p_2,p_3\} \subset \mathbb Z $ and I want to describe how it changes in time. Informally, the rule is simple: At every time-step, subtract ...
0
votes
0answers
27 views

Recurrence Relation With Non-constant Coefficient

I have a question that involves finding the closed form of the generating function for this sequence $$na_n = 3a_{n-1} -4a_{n-2}+ \frac{8.3^{n-2}}{(n-2)!}$$ with $$a_0=2, a_1=6$$ My lecturer told me ...
0
votes
1answer
33 views

Can someone explain the particular solution for non homogeneous recurrence relations?

This is the recurrence relation: $a_n=5a_{n-1} - 6a_{n-2} + 4^n + 2n + 3$ for $n\geq2$ , $a_0 = 5, a_1 = 19.$ I get the general solution. $ c_n = C_12^n+C_23^n.$ The particular solution is in the ...
1
vote
2answers
28 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 ...
0
votes
1answer
32 views

How many words of length n over the alphabet {a,b,c} such that the sub-word aa does not appear?

The question asks that it be solved as a recurrence relation, as in set up a recurrence relation then determine initial values to give a solution. However I am not really confident setting up ...
3
votes
1answer
66 views

Find limit recursion of sequence $x_{n+1} = \frac{x_n+ n x_{n-1}}{n+1} $

Prove sequence $$x_{n+1} = \frac{x_n+ n x_{n-1}}{n+1} $$ $$x_0 = 0, x_1 = 1 $$ converges and find it's limit My attempt Let's prove $0 \le x_n \le 1$: $x_n \ge 0 $ (obvious) By ...
0
votes
0answers
18 views

Help with a proof of the computability of the monus function by recursion

Reading a text on computability by a guy called Cutland, and he basically asserts the following, which is suppose to be a proof by recursion that x ∸ 1 is a computable function: (1) 0 ∸ 1 = 0 (2) ...
2
votes
2answers
43 views

Find general formula for $a_{n+1} = \frac{a_n}{1+n a_n}$

$a_{n+1} = \frac{a_n}{1+n a_n}$ $a_0=1$ Series: $1, 1/2, 1/4, 1/7, 1/11, 1/16...$ ( we ca rewrite as $a_{n+1} = \frac{1}{\frac{1}{a_n}+n}$) By wolfram alpha answer is $\frac{2}{(n-1)^2+n+1}$ I ...
1
vote
2answers
44 views

Restrictions for rule of general sequence: $T_{n+2}=T_{n} + T_{n+1}$

This is a rule which gives a sequence where $11$ times the seventh term ($11 t_7$) is equal to the sum of the first $10$ terms ($s_{10}$), where the first two starting numbers can be chosen. Do any ...
-2
votes
1answer
83 views

How to solve given recurrence relation?

From the following recurrence relation: $a_n =- a_{n-1}+8a_{n-2}+12a_{n-3}+25\cdot3^{n-2}-18n^2+48n+14$, for $n\geq3$ Where $a_0=6, a_1 = 0 $ and $a_2=57$. My attempt: I have generated a ...
0
votes
1answer
39 views

Help with generating functions

I've got two questions. I'm trying to extract the "coefficients" of a power series. I think my terminology is incorrect here but here is what I mean. Here are some examples A(Z) = 1/(1-Z) ...
0
votes
0answers
43 views

Sum of Sequence Involving Fibonacci Sequence

I have a sequence with explicit formula $b_n = F_{n+4} -(n+3)$ The question asks me to use that formula to hence find the following sum for each $n$: $$nF_1 + (n-1)F_{2} +(n-2)F_3 +...+2F_{n-1}+F_n $$ ...
1
vote
1answer
28 views

Solving a third-order homogeneous recurrence relation with variable coefficients

I'm working on a problem that I've managed to reduce to a third-order homogeneous recurrence relation given by the following expression: $$(n + 3) f_{n + 3} - 2(n + 2) f_{n + 2} + (n - 1) f_{n + 1} + ...
1
vote
1answer
31 views

Non-homogeneous Recurrence Relation with Fibonacci Sequence

I have this question in my assignment, I'm just not sure how to handle finding the closed form fully. I have most of it. Here's the question for context. Recall that the Fibonacci sequence is defined ...
0
votes
1answer
37 views

continuous evolution

I have a discrete evolution equation such that $$\rho(t+\tau) = M_0 \rho(t)M_0^\dagger+M_1 \rho(t)M_1^\dagger$$ $M_0\;\&\;M_1$ are two operators such that $tr(M_0^\dagger M_1)=0$ i.e. they are ...
1
vote
1answer
40 views

Finding the general term

I'm having some trouble with trying to find the general term of this sequence. It has a non-linear recurrence. I would really appreciate it if anyone could help me! $ a_{n}= ...
1
vote
2answers
48 views

Find and solve simultaneous recurrence relations for determining n-digit ternary sequences whose sum of digits is a multiple of 3

I'm studying recurrence relations, and I ran into the following problem: Find and solve simultaneous recurrence relations for determining $n$-digit ternary sequences whose sum of digits is a multiple ...
4
votes
1answer
51 views

Assuming $0 \leq a_{n+1} \leq c_n a_n + b_n$ (+ other conditions), show $a_n \to 0$

In the paper "A primal-dual splitting method for convex optimization ..." (see here https://www.gipsa-lab.grenoble-inp.fr/~laurent.condat/publis/Condat-optim-JOTA-2013.pdf), Lemma 4.6 states the ...
24
votes
1answer
270 views

Is there an easy way to see that this simple recurrence is 9-periodic?

In a colloquium talk yesterday, Robert Bryant pointed out that for all initial values $a_0, a_1 \in \mathbb{R}$, the sequence generated by the recurrence relation $$ a_{n+1} = |a_n| - a_{n-1} $$ turns ...
0
votes
1answer
55 views

Recurrence proof problem

I need to show that $a_n= 2^n + a_{n-2}$ for $n$ is greater than or equal to $2$. Prior to that we are told that recursively define $a_0 = 1,\, a_1 = 3, a_2 = 5,\, $ and $ a_n = 3a_{n-2} + 2a_{n-3}$ ...
0
votes
1answer
43 views

Finding a recurrence that satisfies a sequence

Consider the sequence: $1,1,1,3,5,9,17,31,\ldots$ Find both a recurrence and a different sequence that satisfies this recurrence. Saw a decent pattern until the 31 appeared...Pretty ...
0
votes
1answer
34 views

Find a recurrence relation and associated generating function for the number of different binary trees with n leaves

Find a recurrence relation and associated generating function for the number of different binary trees with n leaves. I'm learning about recurrence relations, and I'm struggling more with defining my ...
0
votes
1answer
21 views

How to find equation for this sequence of numbers?

I have a sequence of numbers 0, 1, 5, 19, .... This is the pseudocode to generate the sequence $c = 0$ for $i=0, 1, 2, ...:$ $ c = 3c + 2^i$ Does anyone know how I would write an equation ...
1
vote
0answers
24 views

Hermite Polynomial

In a famous paper by Ait-Sahalia I have found this expression for the Hermite polynomial (pp 252, line -5): $$ H_{j+1}^{\prime}\left(z\right)=-(1+j)\,H_j(z)\quad (1) $$ where $H_j$ is the $j$-th ...
0
votes
3answers
51 views

explicit formula for $a_n$ and $b_n$ [duplicate]

Let $a_n$ and $b_n$ be natural sequence such that $$a_n+b_n\sqrt3=(1+\sqrt3)^n$$ How can I find explicit formula for $a_n$ and $b_n$
5
votes
2answers
144 views

Deducing the closed form for pentagonal numbers

Consider the sequence: $0,1,5,12,22,35,51,70,92,117,145,176,\ldots$ Find both a recurrence and a closed form for this sequence. I've done some research and found out that the majority ...
0
votes
0answers
20 views

How to calculate three constants in linear recurrence

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 ...