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

learn more… | top users | synonyms (2)

0
votes
3answers
80 views

Calculus: Converge of a recursive series?

I'm going crazy to solve this problem: I've a sequence defined by: $$x_1 = 1$$ $$x_2 = 2$$ $$x_{n+2} = \frac{1}{2}(x_{n}+x_{n+1})$$ And I have to prove that this sequence converges and what is its ...
0
votes
1answer
142 views

Result of a $2D$ random walk with position dependent probabilities of step

I was just wondering about $2D$ random walks when I got the idea of a position dependent $2D$ random walk:- A man is initially at $(x,y)$ and can move in a line parallel to the X and Y-axis only. ...
1
vote
1answer
48 views

How can find this two sequence recursive relations?

Let $$D_{n}=\sum_{j=0}^{n-1}(-1)^{n+j-1}\dfrac{\binom{2n-4}{j}}{n+j-1},E_{n}=\sum_{j=0}^{n-1}(-1)^{n+j-1}\dfrac{\binom{2n-4}{j}}{n+j}$$ I want find $D_{n}$ and $E_{n}$ recursive relations, I ...
1
vote
2answers
29 views

Simplification of an Equation with Recurrence Relations

I'm reading through examples on this site. In example 2_2, given the recurrence relation $A_n - 2A_{n-1} = 2n^2$, the guess for the particular solution is $A_n= Bn^2 + Cn + D$. Substituting that into ...
2
votes
1answer
101 views

Recurrence relation / recursive formula / closed formula for partition numbers (1,2,3,5,7,11,15,22,30,42,…)

I have already read this: Number partition - prove recursive formula But the formula from the above link requires a parameter k which is the required number of ...
1
vote
1answer
18 views

Inequality for recursive-defined values

$f_{n+2} = \frac{6}{5}f_{n+1}-f_{n}, f_0 = 0, f_1 = 1$ I need to prove that $f_n < 5/4$ I found that $f_{n} = \frac{1}{8} i 5^{1-n} \left((3-4 i)^n-(3+4 i)^n\right)$ and spend much time for ...
0
votes
1answer
48 views

I do not understand Recurrence Examples on donald knuth's concrete mathematics last page on chapter 1 [closed]

Example 1: When $n = 100 = (1100100)_2$ our original josephus values $\alpha=1,\beta=-1,\gamma=1$ yield: Answer: $ n = \qquad(1\qquad 1\qquad 0\qquad 0\qquad 1 \qquad 0\qquad 0)_2\quad=\quad 100\\ ...
0
votes
2answers
129 views

Sequences of sums of Pascal's triangle

The sequence $$ 1,3,6,10,16,28,56,120,256,528,1056 $$ is defined in OEIS as "sum of every 4th entry of row n in Pascal's triangle, starting at "n choose 2"". It satisfies the recurrence $$ a(n) = ...
1
vote
2answers
36 views

Solving a recurrence relation (textbook question)

$a_{n+1} - a_n = 3n^2 - n$ ;$a_0=3$ I need help for solving the particular solution. Based on a chart in my textbook if you get $n^2$ the particular solution would be $A_2n^2 + A_1n + A_0$ and $n$ ...
0
votes
0answers
32 views

Does this problem have analytic/approximate analytic solution?

Define $F[i]=F[i-1]-F[i-1]^c$ with $F[0]=r>0,c\in(0,1)$. Define $R(r,c)=\min\{i:F[i]<1\}$. What is solution to $c\in(0,1)$ in $R(r,c)=r^{1/k}$ with some given $k>1$?
0
votes
0answers
31 views

Riccati Finite Difference Equation:

Question: Consider the finite difference equation in Zeilberger notation: $$D_{1,x} [y] = a_0(x) + a_1 (x) y + a_2 (x)y^2 $$ Which in functional form is: $$ y(x+1) - y(x) = a_0(x) + a_1 (x) y + ...
1
vote
1answer
50 views

$f(n)= \Sigma_{A \subseteq N} \Sigma_{B \subseteq N}$

for positive integer n we have: $N={1,2,...,n}, f(n)= \Sigma_{A \subseteq N} \Sigma_{B \subseteq N} , |A \cap B|$. for example, how I can calculate $f_5$? I have ...
0
votes
0answers
39 views

Fibonacci polynomial summation

The $n^{th}$ value of a polynomial ($S_n$) of order $k$ is a polynomial in $x$ is given by : $\left(\frac{S_n}{x^n}\right)$= $\sum_{j=0}^n \left(\frac{{F_j}^k}{x^j}\right)$ Where ${F_j}$ is the ...
0
votes
1answer
26 views

Formula for weighed geometric sum

I'm trying to find an easy way to derive a formula for: $S_{n} = \frac{1}{n}\sum_{i=0}^{n}(n-i)x^{i}$ I've found a recurrence relationship of sorts: $S_{n+1} = \frac{xnS_{n}+n+1}{n+1} = ...
0
votes
1answer
47 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
0answers
60 views

Strong induction proof problem with $x$-cent postage stamps

I have the following example problem that has to be proven using strong induction: "Prove that every amount of postage of $12$ cents or more can be formed using just $4$-cent and $5$-cent stamps." ...
0
votes
2answers
62 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
26 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
20 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
86 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
26 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
37 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
36 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
220 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
49 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
73 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
120 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
36 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
63 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
86 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
42 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
213 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
62 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
20 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
25 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
65 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
75 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
112 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
37 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
19 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'? ...