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

learn more… | top users | synonyms (2)

0
votes
1answer
68 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 ...
1
vote
2answers
46 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
38 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
25 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
52 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
14 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
34 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 ...
0
votes
0answers
31 views

Summation Reduction

Given \begin{align*} a_{0} = a_{1} = \frac{3}{2} \hspace{10mm} m a_{n+2} = a_{n}^{3} + (m-3) a_{n} + 2 \end{align*} then find the value of the series \begin{align} \sum_{n=0}^{\infty} \frac{a_{n} + ...
5
votes
2answers
219 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
46 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
41 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
71 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
112 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
33 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
62 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 ...
0
votes
0answers
19 views

Solving a recurrence asymptotically.

How can one solve the following recurrence asymptotically - that is, how can one find an explicit function $f(n)$ such that $T(n) = \Theta(f(n))$? $T(n) = \begin{cases} \Theta(1) & \text{if ...
0
votes
1answer
84 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
31 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
41 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 ...
0
votes
0answers
13 views

Closed form of chained Stationary Functions

Consider the following operator $$D_{(a-1)x,x}\left[ f \right] = \frac{f(ax) - f(x)}{(a-1)x} $$ It's pretty easy to see that a nontrival function $g(x)$ such that $$D_{(a-1)x,x}[g] = g$$ Is given ...
5
votes
1answer
210 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; \\ ...
0
votes
0answers
14 views

Recurrence relation involving ordinary generating function

Let $f_1,f_2,\ldots$ be a given infinite sequence of functions. Define the sequence of functions $F_1,F_2,\ldots$ by the recurrence relation $$F_n(x)=f_n(x)\sum_{k=0}^\infty F_{n+1}(k)x^k$$ or ...
2
votes
2answers
60 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
0answers
17 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
23 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
53 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
74 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
97 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
36 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
18 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
44 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
55 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
48 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 ...
0
votes
1answer
48 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
45 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
28 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
136 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
31 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
20 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. ...
5
votes
2answers
100 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
0answers
23 views

Solution to functional recursion equation

What is solution to following recursion when $c,d\geq1$ fixed? $$F(2^r)=cF\Big(2^{r-1}\Big)+F(2^{r-\frac{1}{r^d}}\Big)?$$
0
votes
1answer
45 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
80 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 ...
-2
votes
1answer
37 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)$?
0
votes
2answers
47 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
36 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
39 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
53 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
22 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 ...
2
votes
1answer
23 views

Distinct Real Roots of $2^{nd}$ order linear homogeneous reccurence relation

I'm currently being introduced to $2^{nd}$ order linear homogenous recurrence relations for the first time. I was working through a first example in my textbook and came into some trouble. Here is the ...