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

learn more… | top users | synonyms

0
votes
2answers
86 views

Repertoire Method. How to know when equations are valid

I'm trying to work a few examples from the Repertoire Method from the Book Concrete Mathematics. I'm working through the following recurrence: $f(0) = 1$ $f(n) = 2f(n-1) + n$ Which I generalized ...
2
votes
2answers
74 views

proof with recurrence relation

How can we proof that number ternary strings that do not contain two consecutive 0s or 1s is $a_n = 2a_{n-1} + a_{n-2}$ What I tried so far: Let $a_n$ be the number ternary strings that do not ...
1
vote
1answer
61 views

recurrence relation related problems

I'm having some difficulties of finding the recurrence relations of; number of divisions of internal region of n sided polygon number of paths from one point to another point in an NxN grid Can ...
0
votes
1answer
43 views

What's the maths symbol for alternation of product and sums?

Is there a mathematics symbol for referring to the equation below? (((((((((((100*y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x = 0, x = 9.8 I've tried using capital ...
3
votes
1answer
55 views

Equivalent of a recurrence sequence [duplicate]

Let $x_{0} = 2$ and $x_{n+1} = x_{n} + \ln(x_{n})$, how can I find an asymptotic equivalent of this sequence say, to the third term? (This is not homework, it was a problem in the Oral Examination ...
1
vote
0answers
402 views

Recurrence relation question

A country uses as currency coins with values of 1 peso, 2pesos, 5 pesos, and 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. a) Find a recurrence relation for ...
2
votes
1answer
240 views

Recurrence relations question

A vending machine dispensing books of stamps accepts only one-dollar coins, $1 bills, and $5 bills. a) Find a recurrence relation for the number of ways to deposit $n$ dollars in the vending machine, ...
0
votes
3answers
96 views

Solve the recurrence $ T_{n + 1} = T_{n} + nT_{n - 1}$

Solve the recurrence $$ T_{n + 1} = T_{n} + nT_{n - 1}\,, \quad\mbox{for}\quad n \geq 1\quad \mbox{with initial conditions}\ T_{0} = T_{1} = 1 $$ by finding the exponential generating function and ...
0
votes
1answer
68 views

Derangement problems [duplicate]

d(1)=0,d(2)=1,d(3)=2,d(4)=9,d(5)=44 Verify that d(5) = 44 and thus that the probability of a random rearrangement of 5 objects being a derangement is 44/120 = 0:3666 So i've been trying ...
0
votes
1answer
44 views

Recurrence – Substitution

Find the asymptotic tight bound in $$ T(n) = 4T\left(\frac{n}{2}\right) + n^{2}\log n. $$ where $ \log n= \log _{2}n $ and $T(1) = 1$. I should solve this using substitution method. I used $n = ...
4
votes
2answers
1k views

Recurrence relation for number of bit strings of length n that contain two consecutive 1s

I'm pulling my hair out over a review question for my final tomorrow. Find a recurrence relation (and its initial conditions) for the number of bit strings of length n that contain two consecutive ...
2
votes
1answer
26 views

Find a direct way to calculate recursive elements (simple problem with matrices)

I nearly solved this question, I just need a hand with the last part since it is a bit confusing. We are given the recursive sequences $\{a_n\}$ and $\{b_n\}$ like this: $a_1=1$, $b_1=2$ ...
1
vote
2answers
200 views

Find recurrence relation for ternary strings that don't have substrings 00, 01 and last symbol is not 0

I am preparing for my finals for discrete mathematics and I came across this exercise in textbook. Let $s_{n}$ denote all ternary strings of length $n$, such that any string in $s_{n}$ does not ...
1
vote
1answer
53 views

Convergence of a sequence with repeated sines [duplicate]

Let $x\in(0,\pi/2)$ and $\{a_n\}_{n\in\mathbb N}$ defined recursively as follows: $$ a_0=x, \quad \text{and} \quad a_{n+1}=\sin(a_n). $$ Show that $$ \lim_{n\to\infty}{n\,a_n^2}=3. $$ Note. There is ...
0
votes
1answer
47 views

I need to use RSolve in mathematica to solve recurrence relations [closed]

I need to use the RSolve command in mathematica to solve recurrence relations and then find a9. I looked at documentations and try for about 2 hours no matter what my answer is not coming out right. ...
2
votes
2answers
51 views

Solving non homogenous recurrence relation

Find all solutions of the recurrence relation $$a_n = 2a_{n-1}+ 3^n$$ The $3^n$ is really throwing me off.
1
vote
2answers
44 views

Solving a recurrence relation in 2 variables

Given this sequence $Q_1(x)=x$, $Q_{n+1}(x)={Q_n(x+1)\over Q_n(x)}$, with $n>=1$, how can I get the explicit n-th term relation? More precisely, $Q_n(x)=$ ? (when $n>=0$) I'm eager to learn a ...
3
votes
1answer
101 views

How did wolfram alpha reduce this second order homogeneous recurrence relation?

I have a recurrence relation as follows: $$ d(n+2) = -(n+2)^2d(n) - (2n+5)d(n+1)$$ Setting n=0 and generating a few coefficients gives $ d(0) = a$ $ d(1) = b $ $ ...
3
votes
2answers
96 views

Recurrence Master theorem

Find the asymptotic tight bound in $$ T(n) = 4T\left(\frac{n}{2}\right) + n^{2}\log n. $$ where $ \log n= \log _{2}n $ and $T(1) = 1$. I should solve this using all three common methods: iteration, ...
0
votes
1answer
50 views

Constructing $N$ unit cubes

I was trying to solve the problem of construction $N$ unit cubes, and while searching I came across this sequence at OEIS. This is exactly what I need but I could not find a method to generate the ...
1
vote
1answer
127 views

Devise recurrence formula for restricted strings over alphabet $\left\{0,1,2\right\}$.

Let $A_n$ denote set of strings over characters $\left\{0,1,2\right\}$ of length $n$ which do not contain substring $22$. Moreover let $B_n$ denote set of strings which both do not contain ...
4
votes
1answer
57 views

Non-linear Recurrence relation

I am concerned to solve the recurrence relation $T(n)=nT^2\left(\frac{n}{2}\right)$ with initial condition T(1)=6. I have tried to do some transformation like $N=2^k$ and some other things like that ...
0
votes
1answer
35 views

How to solve recurrence relation equations

How do I solve the following system equations? $x_i = 2x_{i-1} + 3x_{i-2}$, where $i = 1, 2, 3..., x_1 = 3$, and $x_2 = 6$. The answer is $x_i = \frac{3}{4}(3^i - (-1)^i)$. It's easy to solve: ...
0
votes
2answers
50 views

Help to understand method to find a solution to a second order linear recurrence

Here's an excerpt from my lecture notes: Choosing a Particular Solution $$ ay_{t+2}+by_{t+1}+cy_t=f(t)\,,\qquad t = 0, 1,2,\ldots $$ $$ \begin{array}{|c|c|}\hline f(t)&\text{First ...
1
vote
1answer
23 views

Show that $<b_n\sqrt{3}>=a_n$ ($<x>$: rounding function)

I would appreciate if somebody could help me with the following problem Q: Let $(2+\sqrt{3})^n=a_n+b_n\sqrt{3}$ $(a_n,b_n,n\in\mathbb{N})$ . Show that $<b_n\sqrt{3}>=a_n$ ($<x>$: ...
2
votes
2answers
58 views

Combinatorics arrangement on chessboard

How many ways we can fill $n\times n$ chessboard (with any number of pawns) so that out of every two pawns, one of them was to the left and and down from the second? My ideas: I think that this task ...
17
votes
1answer
218 views

Show that $\lim\limits_{n\to\infty}\frac{a_1+a_2+\dots+a_n}{n^2}$ exists and is independent of the choice of $a$

Suppose $f:\mathbb{R}\to\mathbb{R}$ has period 1, and for some $q\in(0,1)$: $$|f(x)-f(y)|\leq q|x-y|\quad \forall x,y$$ Let $g(x)=x+f(x)$, for any $a\in\mathbb{R}$,define the following sequence: ...
1
vote
1answer
28 views

Proving the monotonicity of a recurrence.

Define the following recurrence for $n = 1, 2, \cdots$ $T(n) = ( 1 - \operatorname{H}(\frac{1 - P^{\frac{1}{n}}}{2}))^n$ where $0 < P < 1$ is a constant, function $\operatorname{H}(\cdot)$ is ...
1
vote
3answers
126 views

Can Master Theorem be applied on any of these?

1) $T(n) = 6T(n/2) + 2^{3 \log(n)}$ 2) $T(n) = 8T(n/2) + \frac{n^3}{(\log(n))^4}$ 3) $T(n) = 9T(n/3) + n(\log(n))^3$ Can the complexity for these be calculated with the Master Theorem? I am not sure ...
0
votes
1answer
72 views

How to solve a recurrence relation?

I want to solve the following recurrence relation with Guess method and induction: $T(1) = 1$ $T(n) = T(3n/4) + T(n/5 + 1) + n$ for $n > 1$
1
vote
0answers
76 views

What is common between difference operators and recurent relations?

They say that solutions of recurrence relations are combinations of exponential functions, the series like [1 a a^2 a^3 and etc]. I know that the difference operators have a matrix like ...
1
vote
1answer
65 views

Outcome probabilities for set number of dice rolls with conditional extra rolls

If we are allowed $n$ rolls of a dice, where each roll of 1 gives us an extra roll, what is the probability of rolling m 1s in the sequence of available rolls, and likewise what is the probability of ...
1
vote
1answer
24 views

2nd order homogeneous repeated roots

$$a_{n+2}-6a_{n+1}+9a_{n}= 3^n \quad n\geq 0 \quad a_{0}=2 \quad a_{1}=3$$ Got repeated roots of 3, so $a_{n}= A\cdot3^n+b\cdot (n\cdot3^n)$ how would i calculate A+B when there is $3^n$? Edit: So ...
0
votes
2answers
35 views

2nd order homogeneous difference equation

$$a_{n+2} = 9a_{n+1} - 18a_n,\quad n\geq 0,\,\,a_0=1,\,\, a_1=3$$ I got to the point where i moved all to LHS which gives me $a_{n+2} - 9 a_{n+1} + 18 a_n$ (correct me if I'm wrong). I then ...
0
votes
2answers
50 views

Find sequence shch that $a_n^2=\frac{a_{n-1}^2+a_{n+1}^2}{2} (n=2,3,\ldots) $

I would appreciate if somebody could help me with the following problem Q: Suppose $a_n \in \mathbb{N}$ is natural number such that: $$a_n^2=\frac{a_{n-1}^2+a_{n+1}^2}{2} (n=2,3,\ldots), a_1=10 $$ ...
1
vote
1answer
55 views

Finding the explicit formula for the succession $x_0=2, x_{n+1} = 5x_n$ and proving it with induction

I'm trying to learn about recursion, first with this exercise: Find the explicit formula for the succession $$x_0=2, x_{n+1} = 5x_n$$ So, from what I've seen, I should test a bit. I see that the ...
0
votes
0answers
21 views

Proving the characteristic equation

Consider the recurrence relation: $a_n = \alpha_1 a_{n-1}+\alpha_2 a_{n-2}+...+\alpha_k a_{n-k} ,$ where $\alpha_1 , \alpha_2 , ... \alpha_n $ are constants. 1) Prove that if $b$ is a non-zero ...
3
votes
0answers
44 views

Showing that a number is part of sequence A000275 in OEIS

Consider the sequence of integers defined recursively by $c_0 = 1$ and $$ c_p = \sum_{l = 0}^{p-1} (-1)^{p+l+1} \binom{p}{l}^2 c_l $$ for $p \geq 1$. This is sequence A000275 in the online ...
2
votes
1answer
52 views

Justifying onto function properties

For $m,n\ge0$ let $O(m,n)$ be the number of onto functions a) Explain why $O(m,n)=0$ when $m\lt n$ I said: since O is an onto function it implies that for all elements of n there is atleast one m ...
1
vote
4answers
67 views

How to solve this reccurence relation?

Let a,b,c be real numbers. Find the explicit formula for $f_n=af_{n-1}+b$ for $n \ge 1$ and $f_0 = c$ So I rewrote it as $f_n-af_{n-1}-b=0$ which gives the characteristic equation as $x^2-ax-b=0$. ...
3
votes
1answer
35 views

Finding recurrence relation that do not contain GOAL

Find a recurrence relation and initial conditions for $c_n$, the number of sequences of length $n$ of upper case letters that do not contain GOAL.
3
votes
1answer
89 views

Generating and solving recurrence relations

I am trying to do this question but don't know where to go from here: The question: For $n\ge1$ let $t_n$ be the number of ways to tile the squares of a 2xn checkerboard using 1x2(which can be rotated ...
0
votes
1answer
51 views

Solve the Recurrence Relation of $A_{n+1} = A_n+A_{n-1}$ for $n\geq2$

I am trying to solve some recurrences for an exam that I found from a past final: I am given $A_1=1$ and $A_2=3$. I re-wrote the relation as $A_{n+1} - A_n - A_{n-1} =0$ and found the characteristic ...
1
vote
1answer
32 views

Recurrence relation related proof

Find a recurrence relation for the number of ternary string that do not contain 00 or 11 .
0
votes
0answers
34 views

Is crossdirectional partial tetration of order $n^c$?

The following animation shows a sum of a matrix where the parameter $c=0$ gives a straight line in pink, and as $c \rightarrow 1$ it approaches the Chebyshev $\psi$ function, the blue staircase. This ...
1
vote
0answers
40 views

finding a recurrence relation for tile covering problem [duplicate]

for $n \ge 1$ let $t_n$ be the number of ways to.cover the squares of a 2xn xheckerboard using 1x2 tiles which can be rotated (ie 2x1 tile) and 2x2 tiles. 1x2 tile comes in 5 different colors and 2x2 ...
0
votes
0answers
33 views

Can Maple solve recurrence relations when n is only certain numbers?

If you have an equation $a(n)=a_{n-1}+2a_{n-2}$ only defined when n is powers of 2, how would convey that to Maple that n has a restriction? What if you wanted only $n \ge 2$?
1
vote
1answer
17 views

What does it mean for a reccurence relation to be homogeneous?

I've seen definitions (such as the one here) that state Homogeneous: All the terms have the same exponent. but others (such as this one) claim that if the equation $a_n=\alpha_1 a_{n-1}+\alpha_2 ...
3
votes
2answers
60 views

Does $E^2 \; ( E \approx 1.2640847\ldots)$ equal $D \approx 1.5979102\ldots$?

Does $E^2=D$? Where $E$ is a constant used in the closed form of the Sylvester Sequence (see: Closed form formula and asymptotics) and $D$ is a constant for the closed formula of the sequence A007018 ...
4
votes
1answer
75 views

Generating a recurrence relation

Suppose you have a large collections of red 1x2 tiles, blue 1x2 tiles and green 1x2 tiles. For $n\ge 0$, let $t_n$ be the number of ways to use these to exactly cover the squares of a 2xn checkerboard ...