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

learn more… | top users | synonyms (2)

0
votes
1answer
31 views

Asymptotic upper bound $T(n)=(T(n−1))^2$

The question is to find asymptotic upper bound for recurrence: $T(n)=(T(n−1))^2$ $T(n) = \text{n for n} \leq 2$ My attempt: I've tried to use substitution method and getting: ...
0
votes
1answer
22 views

Calculate $(\Delta^2+\Delta-2)^{-1} (n^3+1)$

Is this part correct: $$(\Delta^2+\Delta -2)^{-1} =\left( -2\left(I-\frac{\Delta^2+\Delta}{2}\right)\right)^{-1}=-\frac{1}{2} ...
0
votes
0answers
10 views

Struggling with Frobenius Solutions

$x^2y''+5xy'+(x+4)y=0$ where $y = \sum_0^\infty c_n x^{n+r}$ a - prove $x=0$ is a regular singular point (done) b - find the r's (done) c - find the solution (stuck) also, I know the r's are both ...
0
votes
1answer
26 views

Find a system of recurrence relations

Find a system of recurrence relations for the number of $n$-digit binary sequences with $k$ adjacent pairs of $1$s and no adjacent pairs of $0$s. Any help on how to go about doing this would be ...
0
votes
1answer
15 views

Prove sequence defined by recurrence relation using induction

Confused at this question, from what I gather strong induction is necessary here to prove this but the algebraic step after the Inductive Hypothesis is where I'm not too sure. Basis: 2 <= a1 = 2 ...
7
votes
0answers
244 views

Is there a way to write this recurrence relation in faster-to-program manner?

I have the following recurrence relation for some coefficients $$b_{n+2} = \frac{1}{(n+3)(n+2)P_0} \sum_{k=1}^n (n-k+2) (n-k+1) b_k b_{n-k+2}, \quad n>1$$ with $b_1$ to $b_3$ and $P_0$ being the ...
2
votes
0answers
50 views

Finding the Generating Function given a Complex Recurrence

I have the following recurrence relation: $G_0=0, G_1=1,$ $$\left(G+\frac{2}{3}\right)^n+\left(G+\frac{1+w_3}{3}\right)^n+\left(G+\frac{1+w_3^2}{3}\right)^n=0, n>1$$ where $w_3$ is the primitive ...
1
vote
1answer
35 views

Find a recurrence expression which solution have $\sin$ or $\cos$.

I, I'm a computer science student of the first course. My teacher have told us to try to find a recurrence equation for the closed-form expression: $$f(n) = 2^n + 3^n \cos\left(\frac{n\pi}{2}\right) ...
1
vote
2answers
60 views

Expansion of $(a_{{0}}+a_{{1}}x+a_{{2}}{x}^{2}+a_{{3}}{x}^{3}+\cdots)^n$

I am looking for a way to obtain the coefficient $c_k$ of $x^k$ in the expansion of $(a_{{0}}+a_{{1}}x+a_{{2}}{x}^{2}+a_{{3}}{x}^{3}+\cdots)^n$. I know it can be done by the multinomial theorem, but I ...
2
votes
0answers
16 views

Is there a formula for nested quadratic functions?

Notation: $f^{(1)} (x) = f(x) \\ f^{(n)} (x) = f\left( f^{(n-1)}(x) \right)$ I'm looking for an explicit function, $f^{(n)} (x)$, where $f(x)$ is an arbitrary degree $2$ polynomial, or a nested ...
8
votes
1answer
76 views

Newton's method for square roots 'jumps' through the continued fraction convergents

I know that Newton's method approximately doubles the number of the correct digits on each step, but I noticed that it also doubles the number of terms in the continued fraction, at least for square ...
1
vote
0answers
29 views

Give and solve a recurrence [duplicate]

The exercise is; There are m functions from a one-element set to the set {1, 2, …, m}. How many functions are there from a two-element set to {1, 2, …, m}? From a three-element set? Give a ...
0
votes
1answer
24 views

Induction proof of a Recurrence Relation?

Consider the following recurrence equation obtained from a recursive algorithm: Using Induction on n, prove that: So I got my way thru step1 and step2: the base case and hypothesis step but ...
0
votes
0answers
26 views

How to find this polynomial explicitly using the given recurrence relation.

Here is a recurrence relation; $P_0(x)=1$ $P_1(x)=x$ $P_n(x)=xP_{n-1}(x)-P_{n-2}(x)$ for $ n\ge2$. For simplicity lets write $P_n$ in place of $P_n(x)$. We are given with ...
2
votes
1answer
60 views

Combinatorial proof of an identity between restricted counts of permutations and derangements

In an answer to Counting permutations with given condition, I showed that the number of permutations of $k$ elements that satisfy $\sigma(i+1)\ne\sigma(i)+1$ is $\frac{!(k+1)}k$, which is the number ...
31
votes
3answers
797 views

Interesting representation of $e^x$

So I discovered the following formula by using the Taylor series for $\ln (x+1)$ $$x= \ln ...
0
votes
1answer
44 views

Find and solve a recurrence relation for the number of matches played in a knockout tournament with $n$ teams, where $n$ is a power of $2$

Find and solve a recurrence relation for the number of matches played in a knockout tournament with $n$ teams, where $n$ is a power of $2$ I have already found a recurrence relation based on the two ...
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
54 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
38 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 ...
1
vote
0answers
36 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
36 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
37 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
41 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
105 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
52 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
80 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
85 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
70 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
45 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
91 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
46 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
24 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
47 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
102 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
40 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
301 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
56 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
41 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 ...