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

learn more… | top users | synonyms (2)

0
votes
1answer
49 views

If $f(n) = af(n/a) + c \log n$, how does $f(n)$ grow?

Question: If $f(n) = af(n/a) + c \log n$, how does $f(n)$ grow? This is an attempt to correct my answer here: Time Complexity of Recurrence : $f(n)=3f(\frac{n}{3})+O(logn)$? It turns out my answer ...
0
votes
1answer
17 views

Integrality and boundness implies periodicity

Let's consider the reccurence $a_{n+r}=c_{1}a_{n+r-1}+\ldots+c_{r}a_{n}, c_{i}\in \mathbb{Z}$. How to prove that if the $a_{n}$ is integer and bounded, then it's periodic? Could someone suggest the ...
0
votes
2answers
66 views

recurrence formula for number of decimal numbers with some restrictions

I ran into a Olympiad Question that so difficult, if $a_n$ be the number of decimal numbers with length $n$ that has no $0$ in the digits and also has not any combinations $11,12,21$, I want to find ...
0
votes
1answer
44 views

Proof by induction of recurrence relation

I've been shown the following proof by induction of $P(n)$ where $n$ is a positive integer presumably. This is in the context of algorithmic analysis. $ P(n):T(n) = \begin{cases} ...
1
vote
0answers
28 views

Discrete Model Finding Stability

For the discrete model $$x_{t+1} = (\lambda +1)x_t +x_t^3$$ Draw a bifurcation diagram (expressing the equilibrium vs $\lambda$ for values of $\lambda$ near zero. I have the bifurcation diagram. It ...
0
votes
1answer
322 views

How to make a cobweb diagram

I am struggling making a cobweb diagram for the function $$x_{t+1}=8x_t/{1+2x_t}$$ So I understand when making the cobweb diagram, that I have to draw the line $y=x$ But where I have trouble ...
2
votes
3answers
56 views

Recurrence relations with factors in recurrence

How would I go about approaching solving a recurrence relation such as: $$a_{n}=2a_{\frac{n}{3}}+1$$ I'm just not sure how to get a general form for a non-recursive solution, can someone walk ...
0
votes
1answer
46 views

problem understanding induction proof for following recurrence sequence $\frac{a_{n-1}+a_{n-2}}{2}$

I've got this recurrence sequence and it's proof, but I'm stuck with the 2nd/3rd step in the induction step. $$a_0:=0, a_1:=1\\ a_n:= \frac{a_{n-1}+a_{n-2}}{2}$$ Show that for all $n\in N$: ...
1
vote
1answer
37 views

Finding the moments of normal variables

How to calculate the moments of a normal random variable with mean $\mu$ and variance $\sigma^2$? Using integration by parts we get the recurrence relation (calling $a_n = E(X^n)$) $$\begin{cases} ...
0
votes
1answer
63 views

Given minimal characteristic polynomial how to derive linear recurrence?

I was able to find minimal characteristic polynomial of the sequence of numbers using Berlekamp-Massey algorithm. For example, for a sequence $$ ...
1
vote
1answer
117 views

Recurrence Relation for the number of lattice paths with an even number of N moves

The Full Question Find a recurrence for the number of lattice paths beginning at $(0,0)$ with steps N and W, and which contain an even number of N steps. My Work A string of length $n$ can end in W ...
0
votes
1answer
95 views

Solving a recurrence relation with special cases

I need help solving the following problem with a recurrence relation. A miner is trapped in a mine with three doors. The first door will lead him to safety in two hours. The second door leads ...
5
votes
2answers
244 views

Method of solving no-homogeneous recurrence equation

I need to obtain a closed form of $M(t)$, satisfying the following recurrence equation: $$M(t+1)=a+bM(t)+\frac{c}{t+1}\sum_{t'=0}^tM(t')+df(t)$$ Where $f(t)$ is a known function and $a$, $b$, $c$ ...
1
vote
0answers
56 views

partial fraction (with factoring involved) in recurrence relation problem

i want to factor the denominator of the function $f(x)=4-23x+21x^2/(1-2x-3x^2)(1-3x)$ so that it takes the form $(1-ax)(1-bx)(1-3x)$. What I've got is $4-23x+21x^2/(1-3x)(1+x)(1-3x)$ but the ...
0
votes
1answer
110 views

Recurrence Relation of n-digit quaternary?

Determine the n-digit quaternary (0,1,2,3) sequences in which there is never a 3 anywhere to the right of a zero. So I know that the answer is $a_{n+1}$ = $3a_{n}$ + $3^n$. I understand why it is ...
1
vote
2answers
101 views

Solve recurrence relation using generating function

I'm trying to solve: $a_{n+1}-a_n=n^2$, $n\le0$ , $a_0=1$ using generating functions. Step 1) Multiply by $x^{n+1}$ $$a_{n+1}x^{n+1}-a_nx^{n+1}=n^2x^{n+1}$$ Step 2) Take the infinite sums ...
3
votes
2answers
360 views

Find a Generating Function for Ordered Rooted Ternary Trees

The Full Question If we let $T=$ the family of rooted ternary trees, $t_n =$ be number of trees in $T$ with $n$ nodes and $T(x) = \sum\limits_{n=0}^{\infty}w_nx^n$ be the generating function of $T$. ...
0
votes
2answers
44 views

Why this method of solving recurrence relation works?

Could anyone explain why we can solve recurrence relations by finding the soltuion of its characteristic equation? I'm talking about the method presented here. Is the proof of the method validity so ...
3
votes
3answers
74 views

Sum with many troubles [duplicate]

I am currently considering a sum $$\sum_{r=0}^{n}{\binom{n}{r} (-1)^{r} (1-\frac{r}{n})^{n}}$$ but have no thoughtful ideas how to start. Maybe it's worth noticing that ...
1
vote
2answers
146 views

Solve $a_{n+1} - a_n = n^2$ using generating functions

The Full Question Using the method of generating functions, solve $a_{n+1} - a_n = n^2$ where $a_0 = 1$ My Research Scanned the website for similar answers, reviewed the following links: Solve the ...
0
votes
1answer
35 views

Fibonacci numbers with even index

$a_{0}=1, a_{n}=a_{n-1}+2a_{n-2}+\ldots+na_{n-n}$ We can see that $a_{n}=\sum_{m=0}^{n}{ma_{n-m}}$. Then $G(z)=1+\sum_{n=1}^\infty (\sum_{m=0}^n{ma_{n-m}) \cdot z^n = ...
0
votes
1answer
81 views

How to solve this recurrence, $T(n) = T(\sqrt{n}) + n$ using recursive tree method?

How to solve this recurrence, $ T(n) = T(\sqrt{n}) + n $ using recursive tree method? I draw the tree and got a sum, $ T(n) = T(1) + ( n + n^{\frac 12} +n^{\frac 14}+n^{\frac 18}+\ldots +1) $ I need ...
5
votes
1answer
227 views

The recurrence $a_k(n) = \sum_{0\leqslant j<n} a_{k-1}(n+j)$

I'm trying to find a closed form expression to the following recurrence relation: \begin{align} &a_k(0) = 0, \quad \forall k\geqslant 1; \\ &a_k(1) = 1, \quad \forall k\geqslant 1; \\ ...
3
votes
2answers
121 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 ...
0
votes
1answer
31 views

solving non-homogeneous recurrence relation

solve the equation $a_n − 4a_{n−2} = −3n + 8$ for initial values $a_0=2, a_1=1$ I'm stuck on finding the particular solution for $a_n$. I tried using the form $a_n = C_1n + C_2$ but that gets me ...
0
votes
1answer
105 views

Recurrence relation - 2 consecutive 0s

I have a question about this question: Recurrence relation find the number of binary strings that contain two consecutive zeros In your answer, No, it takes each bit separately, except for the ...
1
vote
1answer
369 views

Recurrence relation for number of subsets that contain no consecutive integers

I am currently reading my Discrete Math book and I am confused by this particular examples explanation. Can someone help me understand what this part means? Question: Let S = {1,2,3,4,....,n} and ...
2
votes
2answers
108 views

How can I solve this recurrence relation?

Suppose $A_n = n + nA_{n-1}$, How can I figure out an equation for $A_n$ in terms of $n$? Let the base case $A_0 = 0$.
2
votes
1answer
425 views

Finding and solving the recurrence relation of this ternary string.

I am fairly confused with this problem and I am not looking for an answer, but an explanation as to why my initial set up of this problem is incorrect. I believe that once I Understand this bit of the ...
0
votes
0answers
48 views

I have a problem with solving this recurrence relation

I'm solving this recurrence relation: $$ a(n+2)+4a(n+1)+4a(n)\;\; =\;\; 7 $$ where $n\geq 0, \; a(0) = 1$ and $a(1) = 2$. My step is 1)solve for homogeneous solution \begin{eqnarray*} ...
1
vote
1answer
21 views

Recurrence relations and the empty set

I am currently setting up my variables and such for solving a problem and I am a bit confused about this little detail. The question is: How many ways can you make a number using only '1' and '2'? ...
1
vote
2answers
65 views

How to solve the following recurrence

I know others have already posted about this recurrence $T(n) = 2T(n/2) + n\lg n$ on the following these two posts: post1 and post2 However, the style in which they have solved them, is not one with ...
2
votes
3answers
64 views

How to solve nonhomgenous recurrence relation?

I'm studying this topic in advance and I'm working on textbook problems. The problem is simple : Solve the following recurrence relation a) $a(n+1)-a(n)=2n+3$, $n$ is greater than or equal to ...
2
votes
2answers
63 views

Count number of ways kangaroo can jump all points in interval and finish at last point

There is the problem from Flajolet and Sedgewick book "Analytical Combinatorics": "In how many ways can a kangaroo jump through all points of the integer interval $[1,n+1]$ starting at $1$ and ending ...
1
vote
1answer
62 views

Closed form for this 2 variable recurrence?

I'm trying to find a closed form for this two variable recurrence, but Wolfram Alpha does not seem to understand the input. $$ \begin{cases} a_{0,1} = 1 \\ a_{0,i} = 0 \quad \forall i\neq1 \\ ...
0
votes
0answers
69 views

How would I put these recurrence relation terms into a summation?

I was given these terms as part of a recurrence relation and I need to put it into a summation in order to solve it. $T(n)=2^{k}T\left(\dfrac{n}{2^{k}}\right) + 2^{k-1}T\left(\dfrac{n}{2^{k-1}}\right) ...
0
votes
1answer
33 views

Is there a formula for the summation of this form?

I am doing recurrence relations and I have done some work to get the summation $$\sum\limits_{i=0}^{k-1}16^{i}\left(\dfrac{n}{4^i}\right)^2.$$ I know that there is a formula if the summation was just ...
4
votes
3answers
160 views

Can't solve a recurrence

I am trying to solve the following recurrence: $$T(n) = 9T(n/3)+n^2$$ If I use the master method, I get $n^2\log{n}$ But, I am trying to solve it using substitution. When I try solving it this way, ...
0
votes
2answers
34 views

What is the length of a polynomial taken to a power (multiplied by itself)?

Let's say I have a polynomial $B(x)$. Its length is $m$ (By which I mean, if you write out the sequence of $a_i$'s where $B(x) = \sum_{i=0}^{m-1} a_ix^i$ the length of that sequence is $m$.) So you'll ...
1
vote
0answers
22 views

Recurrence Relation / Difference Equation Problem

I am trying to solve the following recurrence relation, but I am doing something wrong all the time when trying to find the particular solution, and I cannot figure out what. ...
6
votes
2answers
229 views

A recurrence relation problem: $\frac {a_{n-1}.a_{n+1}} {a_n^2} = 1 + \frac 1 n$

I need to solve this recurrence problem to find $a_n$ $\dfrac {a_{n-1}.a_{n+1}} {a_n^2} = 1 + \dfrac 1 n$ It is what I tried so far: $$\log (\dfrac {a_{n-1}.a_{n+1}} {a_n^2}) = \log(1 + \dfrac 1 ...
0
votes
1answer
60 views

About solving a second order difference equation [duplicate]

Let $r>4$ be a positive integer. I want to solve this difference equation: $$u_{n+1}-r²(1+r²ⁿ⁺¹)u_{n}+r²r²ⁿ⁺¹u_{n-1}-2r²r²ⁿ⁺¹=0$$ but I have no a good idea to start.
0
votes
1answer
149 views

Recurrence Equation Solution / Difference equation - WolframAlpha

I am given the recurrece equation $y_k-7y_{k-1}=5^k$ and found the (hopefully correct) particular solution to be $y_k^P=-\frac{5}{2}5^k$ WolframAlpha, however, gives the particular solution ...
-1
votes
1answer
43 views

Transformations solving recurrence with generating functions

Why is $\sum_{n ≥3} a_{n-1} z^{n-1}$ equal to $(A(z) − 1 − z)$? $\sum_{n ≥3}a_{n-2} z^{n-2}$ equal to $(A(z) − 1)$?
1
vote
0answers
37 views

orthogonal polynomials: explicit representation

Consider a sequence of orthogonal polynomials $P_0(x) = 1$, $P_1(x) = x$, and recursively $P_{n}(x) = (a_n x + b_n) P_{n-1}(x) + c_n P_{n-2}(x)$ for some sequences of real constants $a_n$, $b_n$, ...
0
votes
2answers
55 views

How to deduce sum's result?

I was solving some tricky-task with algorithms and I obtained following reccurence: $$a_{k+1} = 4a_{k} + 16^{k}, a_{1} = 1$$ It's obvious that with given start condition: $$a_{k+1} = 4a_{k} + 16^{k} ...
0
votes
0answers
43 views

Does this tridiagonal system have a closed-form solution?

Let $$ A = \begin{pmatrix} a + c_1 & -b\\ -a & a+b+c_2 & -b\\ & -a & a+b+c_3 & -b\\ & &\ddots & \ddots & ...
0
votes
1answer
88 views

Iterative Logarithm in Recurrence Relation?

Anyone Could describe me How we can solve this recurrence relation? $T(n) = T(\log n) + O(1)$ $T(1) = 1$ a) $O(\log n)$ b) $ O (\log^* n) $ c) $ O (\log^2 n) $ d) $ O (n / \log n) $ Our TA ...
1
vote
1answer
67 views

Solve recurrence relation

Solve the following recurrence. First transform it to a simpler recurrence and then solve the new recurrence using generating functions or a characteristic polynomial: $f_n = f_{n−1} · f_{n−2}$ for $n ...
0
votes
1answer
43 views

Understanding the subsets without consecutive integers are counted with fibonacci numbers

I'm working my way though a section on Second-Order Linear Homogenous Recurrence Relations with Constant Coefficients. There is an example that I do not understand. The part I'm having trouble with is ...