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

learn more… | top users | synonyms (2)

3
votes
2answers
34 views

How can I prove that a linear recurrence $x_{n+1} = αx_n - β$ will contain a composite number in the sequence?

I'm working on a homework problem about finite automata and I got stuck trying to prove a fact about prime numbers that I think should be true. Given a prime $p$ and integers $α$ and $β$, can I show ...
0
votes
0answers
50 views

Comparison between roots of two polynomials

Let $m,n,p$ be natural number greater than $2$. Consider $$f(x)=(x-p+1)(x-m+1)(x-n+1)-x(2x-m-p+2)$$ We also have $g(x)$ which is obtained by changing $m$ to $m+1$ and $n$ to $n-1$ in $f$, i.e. ...
1
vote
2answers
29 views

Find a recurrence relation for the number of $n$-digit binary sequences with no pair of consecutive $1$s

Find a recurrence relation for the number of $n$-digit binary sequences with no pair of consecutive $1$s. I know my base case:$$a_1 = 2$$ for either $1$ or $0$. Normally to construct the recurrent ...
0
votes
0answers
33 views

Given $3$ different speeds, find a recurrence relation for the number of ways to travel $n$ miles

You can walk $3$ miles per hour, jog $5$ miles per hour, or run $10$ miles per hour. You go a full hour before you can change pace. At the end of each hour, you make a choice as to whether to walk, ...
0
votes
1answer
26 views

Find a recurrence for the number of ways to arrange cars in a row with $n$ parking spaces

Find a recurrence for the number of ways to arrange cars in a row with $n$ parking spaces if we can use Cadillacs or Hummers or Fords. A Hummer requires two spaces, while a Cadillac or Ford requires ...
1
vote
2answers
50 views

Explicit formula from for interesting reccurence

$$t_0=-5, t_1=\frac{11}{5} $$ $$t_n=1-\frac{2}{t_{n-1}} + \frac{-4}{t_{n-2}*t_{n-1}} $$ I have never seen so uncommon formula for recurrence like this before. I have no idea how to solve it. Please, ...
0
votes
1answer
33 views

Tower of Hanoi Problem: Two Dimensions

I'm reading Knuths Concrete Mathematics and trying to solve my own questions as I read through the book. Right now, I want to solve a variant of the tower of Hanoi problem - solving for minimum number ...
1
vote
0answers
12 views

Recurrence tree diagram

I can generally do these but I feel like I'm missing a very basic piece of information. For example, the recurrence $T(n) = 2T(n/2) + n$ is easy to draw out in a tree diagram, but for some reason I ...
1
vote
1answer
40 views

How to calculate general formula for this recurrence?

The recurrences are $$F_n = a F_{n - 1} + b G_{n - 2}$$ $$G_n = cG_{n - 1} + d F_{n - 2}$$ $$H_n = e F_{n} + f G_n$$ where $a, b, c, d, e, f$ are constants. How do I calculate $H_n$ in terms of only ...
1
vote
1answer
29 views

Closed formula for finite product series

I need to solve the recurrence: $$ \begin{align*} T(n) &= kT\left(\frac{n}{2}\right) + (k - 2)n^3 \\ &\textit{where}\; k \in \mathbb{Z}: k \geq 2 \\ &= ...
7
votes
1answer
104 views

$2005$th derivative of $f$ at $0$

So I tried using Leibnitz formula to solve by recurrence, but I can just get to one point and then it's a mess again. Problem is Let $f(x)=\frac{1}{1+2x+3x^2+\ldots+2005x^{2004}}$. Find ...
0
votes
0answers
12 views

Recurrence: how to compute the base case when $n$ is its root on each step?

Sorry for maybe vague title, please feel free to change it, if you think you have a better one. I need to solve this recurrence, and this is what I've done so far: $$ \begin{align*} T(n) &= ...
0
votes
1answer
49 views

Partial fraction of a generating function

I am solving a recurrence relation $a_0 = a_1 = a_2 = 1, a_{n+3} = a_{n+2} − 2a_{n+1} − 4a_n$ for $n \ge 0$ I got a generating function for this sequence $f(x) = \frac{2x^2+1}{4x^3+2x^2-x+1} $ ...
0
votes
1answer
78 views

Truncating a taylor expansion for a recurrence relation?

Let's say I have a function $N$ whose future value at a time $t + t_{d}$ obeys the relation $N(t + t_{d}) = A(t)N(t)$ where $A(t)$ is also a function of $t$ whose value can be calculated. One can ...
0
votes
2answers
84 views

Two dimensional recurrence relation

I'm struggling to get the following recurrence relation into a closed form if possible: $$f(n,n)=1$$ $$f(n,1)=(n-1)!$$ $$f(n,k)=f(n-1,k)\cdot(n-1) + f(n-1,k-1)$$ where $f$, $n$ and $k$ are positive ...
1
vote
2answers
24 views

Dichotomy in the number of regions on a plane formed by an infinite number of lines

I'm reading Knuth's Concrete Mathematics and we are dealing with recurrence relations. He proves that the number of regions $L_n$ formed by $n$ lines on a plane is $L_n=\frac{n(n+1)}{2}$. I don't ...
1
vote
5answers
69 views

recurrence relation unable to solve

I am trying to solve recurrence relation : $$z_n = 2z_{n-1} + z_{n-2} \;\;\;\;\;z_0=1\;\;\;z_1=3$$ Could you please help to provide a solution. I got stuck with Lamdas.. Are there some simple ...
0
votes
0answers
19 views

What is the maximum number $L_n$ of regions formed on the plane by $m$ identical zigzags/fences, each with n components.

I've just started reading through Knuth's Concrete Mathematics and am dealing with recurrence relations. The book talks about solving the recurrence relation for the number of regions formed by n ...
0
votes
1answer
44 views

Not sure what I'm doing wrong with this recurrence problem

$r_{n} = 4r_{n-1} + 6r_{n-2} $ Using Generating Functions I have: We have $ R(x)= \sum^{\infty}_{i=0}r_nx_n $ $R(x) = \sum_{i=0}^{\infty} r_nx_n $. Then we multiply the relation on both sides by ...
3
votes
3answers
88 views

The number of words of length $n$ from specific alphabet with rule of creating.

Determination of the number of words of length n formed from the alphabet $\{ a, b , c, d \} $, where the letters $a , b $ are not adjacent. How to find out a recurrence and explicit formula for it ? ...
3
votes
4answers
39 views

Find the solution to and limit of $a_{n+1} =\frac{v}{a_n+w} $ with $a_1>0, v > 0, w>0$

Find the solution to and limit of $a_{n+1} =\frac{v}{a_n+w} $ with $a_1>0, v > 0, w>0$. This was inspired by my answer to Converging sequence $a_{{n+1}}=6\, \left( a_{{n}}+1 \right) ^{-1}$. ...
0
votes
0answers
23 views

Advancement Operator question

Are all solutions to linear recurrence equations of the form f(n) = c0(a1)^n + c1(a1)^n + c2(a2)^n ... + cn(an)^n? I solved one question where the initial condition was s0 = 3 and s(n+1) = 2sn. Is ...
4
votes
1answer
46 views

How many base $10$ numbers are there with $n$ digits and an even number of zeros?

How many base $10$ numbers are there with $n$ digits and an even number of zeros? Solution: Lets call this number $a_n$. This is the number of $n-1$ digits that have an even number of zeros ...
4
votes
4answers
100 views

Does the Pell-like equation $X^2-dY^2=k$ have a simple recursion like $X^2-dY^2=1$?

If $d \ne 0$ is a non-square integer, and $(u,v)$ is an integer solution to the Pell equation $$ X^2 - dY^2 = 1, \tag{$\star$} $$ then each solution $(x_i,y_i)$ can be recursively calculated using ...
1
vote
1answer
39 views

Alternating sign odd number generating function.

I have a sequence that I'm trying to find both an ordinary generating function for as well as a closed form without a floor function. The sequence $$\{1,1,-1,3,-3,5,-5,7,-7,9,-9,11,-11,\}$$ is ...
5
votes
1answer
216 views

Is there a way to solve explicitly the following functional equation?

I want to find an unknown function (actually CDF) $F(p)$ which solves $1 - \lambda F(\frac{q_L}{q_H}p) - (1-\lambda)F(p-[q_H-q_L]) - \frac{K}{p-c_H} = 0$, where $0<\lambda<1$, $q_H > q_L ...
0
votes
4answers
50 views

Determine the generating function $f(x)$, of the recurrence relation..

Determine the generating function of the recurrence relation $a_n=3\cdot2^{n-1}-a_{n-1}$ for $n\geq2 , a_1=0$ So $a_0x+(3\cdot2-a_1)x^2+(3\cdot4-a_2)x^3 \ldots $ and what to do next?
1
vote
0answers
27 views

Partition-Generated Recurrence Relation

Suppose you have a series $\{A_n\}$ with the following recurrence relation: $$A_{n+1} = \sum_{\lambda(n)}\prod_{i=1}^{|\lambda|}A_{\lambda_i}$$ where $\lambda(n)$ is an integer partition of $n$ and ...
1
vote
1answer
55 views

How many ordered subsets of a set?

We have a set $A$ consisting of $n$ elements. Is there a closed form for the total number of subsets when you care about the order of the elements in the subsets? Lets call the number ...
1
vote
0answers
17 views

$f:A\rightarrow B$ and $a_n=f(a_{n-1})$ $L=[a_1,a_2,…a_n,…]$ For which $f$ and $a_0$ is $\bar L=B$?

This is a generalization of a question I posted a few days ago regarding a particular recursive sequence . I am trying to find general conditions (if they do exist) on which the problem has a ...
0
votes
1answer
29 views

Recurrence of $T\left(n\right)=\:T\left(\frac{n}{2}\right)+n$

Recurrence of $T\left(n\right)=\:T\left(\frac{n}{2}\right)+n$ where T(1) = 1. I know the Master Theorem is applicable here, but I have to prove it. I found a question similar to mine on this forum, ...
2
votes
3answers
40 views

How do I find a closed form for this recurrence?

$$a_0=0$$ $$a_n=a_{n-1} + 2n^2-n$$ What I have so far, but I don't think it's right: $$x^n = x^{n-1} + 2x^2-x^{n-1}=2x+x^{n-2}-1$$ $$0=-x^{n-1}+x^{n-2}+2x-1$$
2
votes
0answers
95 views

Prove that $a_{n+1}a_{n-2}-a_{n}a_{n-1}=1$ is always an integer [duplicate]

We are given the sequence $a_1, ... , a_n$ defined by $a_1=a_2=a_3=1$, and $$a_{n+1}a_{n-2}-a_{n}a_{n-1}=1.$$ Prove that $a_k$ is an integer for all positive integers $k$. The most obvious idea to me ...
2
votes
1answer
27 views

How to model this recurrence?

I'm having some problems on how to model this situation correctly, using difference equations. Say there's a medicine that has a half-life of 12 hours (every 12 hours, the amount of it on your blood ...
0
votes
1answer
20 views

check working for recurrence relation

A small engineering company produces nuts and bolts for the commercial market. The newly made nuts and bolts are deburred and washed in a solution of water and acid. The washing solution is ...
0
votes
0answers
18 views

Given T(n) = 16T(n/4) + f(n), find a function f(n), with the solution of T(n)=nlogn

how can i find the correct function? i tried to find a function that matches the third case of the Master Theorem, but it doent matches.
1
vote
0answers
13 views

Prove the conditions that an equilibrium must satisfy:

I'm having problems with my difference equations problem set. The current topic is equilibrium points of non-autonomous equations. Let's see: Consider $y_{k+1}=f(y_{k},k)$, where $f(y_{k},k)$ is a ...
0
votes
2answers
18 views

Show that there is an equilibrium point

Show that if $x_{k+1}=f(x_{k})$, where $f$ is continuous, has two stable equilibrium points, then there's a third equilibrium point between then. I'm trying to approach this problem using the ...
1
vote
2answers
47 views

Solving Recurrence with Generating Function

I have the following recurrence: $r_n = 4r_{n-1} + 6r_{n-2} \text{ where } r_0 = 1 \text{ and } r_1 = 3$ Next, I write my generating function, $R(x)$: $$ \begin{align} R(x)*(1 - 4x - 6x^2) &= ...
1
vote
0answers
21 views

Upperbound for quadratic recurrence equation

I have a quadratic recurrence equation $\forall n \ge 2$ of the form $$ f(n)=\sum_{l=1}^{n-1} f(l)f(n-l), $$ with the initial condition $f(1) =1$. The first few terms of the series are given by ...
1
vote
1answer
29 views
0
votes
1answer
53 views

How to find the general solution of the difference equation [closed]

Take this as an example. Wondering if someone can elaborate their ideas. Thanks a lot!
2
votes
0answers
22 views

Solving recurrence relation, no clue how to approach

I'm trying to solve the following recurrence relation $$T(n)\le T\left(\frac{3n}{4}\right)+T\left(\frac{n}{\log n}\right)+C\cdot{n}\log\log n$$ The answer should be $T(n)=\Theta(n \log\log n)$ ...
0
votes
0answers
32 views

List step by step instructions to turn a properly colored pie of j sectors into a properly colored pie of j+1 sectors

A circular disk is cut into n distinct sectors, each shaped like a piece of pie and all meeting at the center point of the disk. Each sector is to be painted red, green, yellow, or blue in such a way ...
0
votes
2answers
23 views

Solve the following recurrences using backward substitutions: [closed]

Solve the following recurrences using backward substitutions: $x(n) = 3x(n-1)$, for $n > 1$; $x(1) = 4$
3
votes
2answers
29 views

Compute the limit of a recursively defined sequence in terms of its initial values [duplicate]

Consider the sequence $\{ a_n \}$ defined recurisvely in terms of $a_1$ and $a_2$ by $$ a_{n+1} = \frac{a_n + a_{n-1}}{2} $$ for $n \geq 2$. Assuming this sequence converges, find the limit in terms ...
0
votes
0answers
13 views

Citation Resource? Discrete Variation of Parameters

I have a colleague that needs a citation resource for variation of parameters in the discrete setting when solving non homogeneous linear recurrence relations. I have tried googling for it, but I'm ...
0
votes
0answers
18 views

Solving recurrence relation $T(n)\le T(0.9n)+T(0.2n)+O(n)$

I'm trying to solve the following recurrence relation $$T(n)\le T\left(\frac{9}{10}n\right)+T\left(\frac{1}{5}n\right)+\text{O}(n)$$ According to book it should be that $T(n)=\text{O}(n^2)$. I ...
1
vote
1answer
41 views

Relation between two sequences or summations

Let us define two sequences \begin{equation} G_{n}=\sum_{i=1}^n a^{-i}t_{i-1} \end{equation} and \begin{equation} g_{n}=\sum_{i=1}^n t_{i-1} \end{equation} where $a$ is an integer and $t_n$ is an ...
2
votes
4answers
53 views

Solving Recurrence Relation problem

I am trying to solve the recurrence relation: $$G_n = \frac{1-G_{n-1}}{4}$$ $$G_0 = 0$$ $$G_1 = \frac{1}{4}$$ I am told that the answer is $$G_n = ...