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

learn more… | top users | synonyms (2)

2
votes
1answer
57 views

What is the relationship between a non homogenous second order difference equation (constant coefficients) and its derivative?

Here's an excerpt of a lecture note I am reading (I've highlighted the beginning of the part that I don't understand): I don't understand how derivative comes into the picture. Here's some context ...
2
votes
1answer
117 views

Closed form solution to a recurrence relation (from a probability problem)

Is there a closed form solution to the following recurrence relation? $$P(i,j) = \frac{i^{5}}{5i(5i-1)(5i-2)(5i-3)(5i-4)}\sum\limits_{k=0}^{j-5}(1-P(i-1,k))$$ where $P(i,j)=0$ for $j<5$. The ...
0
votes
1answer
70 views

Recurrence relation question - check my answers! Basic questions.

I had a chat with a friend about these questions (they are homework questions) , and we argued about the solution. I would just like an outside opinion about my answers: 1) $n \geq 2$ people are ...
0
votes
1answer
131 views

Recurrence relation - simple question. Homework. Permutations with a twist,

I think I solved it but I would love someone to tell me if I'm wrong. the question is as follows: $n$ people are sitting on a bench with $n$ seats. Find a recursive equation that calculates how many ...
2
votes
1answer
88 views

Recurrence relations - simple questions, please verify my answers.

I'm posting this question because this is new material for me and I am unsure of my answers and have no one to consult with. I solved the first three and would appreciate feedback. I need help solving ...
5
votes
2answers
216 views

recurrence relation $f(n)=5f(n/2)-6f(n/4) + n$

I've been trying to solve this recurrence relation for a week, but I haven't come up with a solution. $f(n)=5f(n/2)-6f(n/4) + n$ Solve this recurrence relation for $f(1)=2$ and $f(2)=1$ At first ...
0
votes
1answer
56 views

Recurrence relation that skips $n-1$?

A difficult question I'm having problems with regarding recurrence relations and recurrence equations. The question is as follows: In how many different ways can I cover a 3xn checkberboard with 2x1 ...
2
votes
1answer
43 views

Solving the recurrence $x_n = \frac{\sum_{i=0}^{n-1} x_i}{2n}$

In my answer over at cstheory.stackexchange.com I set variables according to the recurrence $$x_0=1, x_n = \frac{\sum_{i=0}^{n-1} x_i}{2n}$$ Wolfram Alpha tells me that apparently the solution to this ...
3
votes
5answers
113 views

Simple functional equation

I have a simple functional equation: $$ \alpha(x) = {1 \over 2}\left[\alpha\left(x - 1\right) + \alpha\left(x + 1\right)\right]\,, \qquad \alpha\left(0\right) = 1\,,\quad\alpha\left(m\right) = 0 $$ I ...
2
votes
1answer
102 views

How find this function $f(2^m)=?$

show that:there exists unique function $f:N^{+}\to N^{+}$,such $$f(1)=f(2)=1$$ and $$f(n)=f(f(n-1))+f(n-f(n-1))),n=3,4,\cdots$$ and Find $f(2^m),m>2,m\in N$ My try: let $n=3$ ,then we have ...
0
votes
3answers
323 views

Difficult recursion problem

A student can do the things bellow: a. Do his homework in 2 days b. Write a poem in 2 days c. Go on a trip for 2 days d. Study for exams for 1 day e. Play pc games for 1 day A schedule of n days ...
1
vote
1answer
240 views

Finding explicit formula for recurrence relation?

What would a explicit formula for this sequence? a_k = a_(k-1)/k? The way I find explicit formula is to write out some terms but this time it's not working.. I'd appreciate your help!
1
vote
2answers
114 views

What is the order of growth of the parameterized recurrence relation given below?

Given two parameters $a$ and $b$ (both positive integers), please estimate the order of growth of the following function: $$F(t)=\left\{\begin{array}{ll} 1, \, &t\le a \\ F(t-1) + b\cdot ...
3
votes
2answers
137 views

A proof using $\Delta^ny(t)=\sum_{k=0}^{n}{(-1)^k\dbinom{n}{k}y(t+n-k)}$

Please How can I use $\Delta^ny(t)=\sum_{k=0}^{n}{(-1)^k\dbinom{n}{k}y(t+n-k)}$ to prove $\sum_{i=0}^{n}{(-1)^i\dbinom{n}{i}y(i)}=(-1)^n\Delta^ny(0)$ and hence to evaluate ...
0
votes
1answer
127 views

Summation of falling factorials

I just want to know if I should evaluate $\sum(t+1)^\underline{4}$ the way we evaluate $\sum{t^\underline{4}}$. Thanks.
1
vote
1answer
218 views

Negative falling Factorial

Please can someone tell me what is the value of $1^\underline{-2}$? I know that $1^\underline{2}=0$. Thanks.
3
votes
2answers
64 views

Solve a recurrence relation

The sequence x is defined as follows: $x_{0} = 1, x_{t} =\sqrt{0.2x_{t-1}+0.9x_{t-1}^{2}}$ I want to know what is t when $x_{t} = 2$. I use a spreadsheet to calculate it. When t is 104, $x_{t} = 2$, ...
3
votes
1answer
58 views

Find the number of ways that 2n people may be paired.

Question: Find the number of ways that 2n people may be paired. I have figured this problem out, and I'm fairly certain that there are $\frac{(2n)!}{2^{n} n!}$ ways. However, I cannot seem to work ...
0
votes
1answer
135 views

Generating Function of a Recurrence Relation.

Given a sequence a(n) = a(n -2) , a(0) = 2 , a(1) = -1 Find the generating function What i have done so far: The recurrence relation is going to be a(n) - a(n-2) = 0 A = the generating function A ...
2
votes
3answers
81 views

Solve the recursion $a_{n} = n a_{n-1} + (n+1)!$

Define the sequence $\{a_{n}\}$ by $a_{n} = n a_{n-1} + (n+1)!$ for $n \geq 1$ and setting $a_{0} = 1$. Solve this recursion completely. I can solve this rather easily by an induction argument, where ...
0
votes
2answers
124 views

Prove (1 + x)^n + (1 - x)^n < 2^n by using Binomial Theorem

Hi my boss asked me to resolve this equation: Prove (1 + x)^n + (1 - x)^n < 2^n by using Binomial Theorem -1 < x < 1 ...
1
vote
2answers
77 views

Solving recurrence $T(n)=T(n-1)+3^{n-1}$

I have trouble solving following recurrence. $$T(n)=T(n-1)+3^{n-1}$$ So far I tried annihilators but it doesn't work.
0
votes
2answers
104 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
94 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
68 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
50 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
61 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 ...
2
votes
0answers
1k 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
877 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
99 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
108 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
58 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
2k 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
36 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
406 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
64 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
75 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
63 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
72 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
162 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
160 views

Find the asymptotic tight bound for $T(n) = 4T(n/2) + n^{2}\log n$

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
53 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
200 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
67 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
46 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
56 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
24 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
85 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
238 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
35 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 ...