1
vote
1answer
43 views

Find all solutions of the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 2^n + 3n$

Question: Find all solutions of the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 2^n + 3n$ (Hint: Look for a particular solution of the form $qn2^n + p_1n + p_2$, where $q, p_1, p_2$ are ...
5
votes
1answer
70 views

Expressing a Recursion in terms of factorials

Given the recursion $$f(n) = nf(n-1) + (n-1)f(n-2) $$ $$f(0) = 1, f(1) = 1$$ How exactly does one express the target function? I know that $$f(n) = nf(n-1)$$ gives rise to $$f(n) = \Gamma(n+1)$$ ...
0
votes
0answers
27 views

Concrete math generalized josephus recursion understanding 1.15

I am studying through the josephus problem in concrete math , Here is the equation of binary form $$f(1) = α ;$$ $$f(2n + j) = 2f(n) + β_j ,$$ $$\text{ for } j = 0, 1 \text{ and } n \geq 1$$ this ...
4
votes
0answers
41 views

How to solve a non-homogeneous second-order linear difference equation with both a forward and a backward difference?

Quite a long title for this: I'm looking for the general solution of the following difference equation: $$ax_{t+1} -bx_t + x_{t-1} = c + u_t$$ where $a,b,c$ are real constants and $u_t$ is a bounded ...
0
votes
1answer
67 views

Solving this recurrence relation

please tell me a way to solve this recurrence $$n\cdot R_n=C_1\cdot R_{n-1}+C_2\cdot R_{n-2}.$$ $C_1$ and $C_2$ are constants.. There is an $n$ there in the left hand side.. it makes mess. I tried ...
0
votes
1answer
26 views

Change of variables in function $T(n)$.

I've been given this recurrence to solve: $T(n) = T(\sqrt n) + \theta(lglgn)$ And I'm told that the way to solve it is to let $m = lgn$, so that the recurrence can be rewritten as follows: $S(m) = ...
0
votes
2answers
27 views

Find the values of $r_1, r_2, r_3$ in the recurrence relation $a_n = r_1 a_{n-1} + r_2 a_{n-2} + r_3 a_{n-3} $

Consider the recurrence relation $a_n = > r_1 a_{n-1} + r_2 a_{n-2} + r_3 a_{n-3} $ for $n \ge 3$. The roots of the characteristic polynomial are $x = -1$ of multiplicity 2, $x= 3$ of ...
1
vote
1answer
21 views

Cardinality of a set with a recurrence relation.

Let $A = \left\{ f\in \mathbb{N}\rightarrow \mathbb{C} \mid \forall n\in \mathbb{N}. f(n+3) + 3f(n+1) = f(n+2)+f(n) \right\}$ What is $\left|A\right|$? Well, I tried to treat $f$ as a recurrence ...
3
votes
2answers
56 views

Solving combinatorical problem using characteristic polynomial

How many $6$ length strings above $\left\{1,2,3,4\right\}$ are there such that $24$ and $42$ aren't allowed. The suitable recurrence relation for this problem is: $a_{n+2} = 2a_{n-1} + ...
0
votes
2answers
132 views

Recurrence Relation Solving Problem

Can anyone help me in solving this complex recurrence in detail? $T(n)=n + \sum\limits_{k-1}^n [T(n-k)+T(k)] $ $T(1) = 1$. We want to calculate order of T. I'm confused by using recursion tree ...
0
votes
2answers
41 views

Divide and Conquer Recurrence Relation help?

So the divide and concur recurrence has to be of the form H($n$) = $a$H($n$/$b$) + $cn^d$. I already figured out that $a$ = 4 and $b$ = 2. I am really stuck on how to find $cn^d$ however. I ...
0
votes
1answer
27 views

Particular solution of recurrence relation

I've got this recurrence relation: $$M_n = M_{n-1} + n(2n-1)|M_0 = 0$$ and can't think of any form of particular solution to get a solvable constant. With $M_n^H = K$being the homogeneous part of ...
10
votes
3answers
177 views

Show that $2^n(\cos^n(\frac{2\pi}{9})+\cos^n(\frac{4\pi}{9})+\cos^n(\frac{8\pi}{9}))\in\mathbb{Z}$

$a_n=2^n\left[\cos^n\left(\dfrac{2\pi}{9}\right)+\cos^n\left(\dfrac{4\pi}{9}\right)+\cos^n\left(\dfrac{8\pi}{9}\right)\right]$. Show that $a_n\in\mathbb{Z}$ for all $n\in\mathbb{Z}$. Find the last ...
1
vote
1answer
36 views

Help with recurrence equation

I need to solve the following recurrence equation $p_i =\begin{cases} r(p_{i-1}+p_{i+2}) &\mbox{if } i \text{ is odd} \\ (1-r)(p_{i-1}+p_{i}) & \mbox{if } i \text{ is even} \end{cases} i ...
1
vote
2answers
24 views

Not sure how to do Non-Homogeneous Recurrence Relations

I have a sample exam paper, and the answer is given, but I can't work out the answer from the question: Find the solution of: $a_n = \frac{1}{3}a_{n-1} + 2$ using $a_0 = 4$ Given Answer: $a_n = ...
1
vote
1answer
37 views

Recurrence Relation all general solutions

I need some help solving the following recurrence relation: $a_n = 4a_{n-1} - 4a_{n-2} + (n+1)*2^n$ What I've tried: a) Find the general solution of the associated linear homogenous recurrence ...
1
vote
2answers
106 views

Find an explicit formula for the recursive sequence (tips?)

Problem: A sequence is defined recursively as follows: Sk = 2k - Sk - 1, for all integers k greater than or equal to 1 S0 = 1 Use iteration to guess the explicit formula for the sequence. Use ...
1
vote
1answer
73 views

Need help with recurrence relation

So the question is: "Find a recurrence relation for the number of ways to pick $n$ objects from $k$ types with at most 3 of any one type" I think I figured out what it would be excluding the last ...
0
votes
1answer
120 views

find the recurrence relation (homework)

I'm new to recurrence relations and I'm having trouble figuring out this problem: Find a recurrence relation for the number of ways to make a stack of green, yellow, and orange napkins so that no two ...
0
votes
2answers
28 views

Find $f(n)$ when $n = 2^k$ where $f$ satisfies the recurrence relation $f(n) = f\left(\frac{n}{2}\right) + 1$ with $f(1) = 1$

Given: $f(1) = 1$. Answer: $$f(2) = f(1) + 1 = 1 + 1$$ $$\ldots$$ $$f(4) = f(2) + 1 = 1 + 1 + 1.$$ How do I find the value of $f(n)$ where $n$ is an odd integer? Let say $f(3) = ...
2
votes
2answers
66 views

Finding the recurrence relation for number of ways to deposit n dollars

Question: A vending machine dispensing books of stamps accepts only one dollar coins, 1 dollar bills and 5 dollar bills. a) Find a recurrence relation for the number of ways to deposit n dollars in ...
0
votes
1answer
10 views

How does one find annihilators for recurrence relations?

I've recently taken an interest in the Method of Annihilators for solving recurrence relations. However, I taught myself using nearly solely this Power Point presentation. Thus, my knowledge is ...
1
vote
4answers
46 views

Help understanding Recursive algorithm question

We have a function that is defined recursively by $f(0)=f_0$, $f(1)=f_1$ and $f(n+2) = f(n)+f(n+1)$ for $n\geq0$ For $n\geq0$, let $c(n)$ be the total number of additions for calculating $f(n)$ ...
0
votes
1answer
75 views

Induction Proof of: Find $f(n)$ when $n=2^k$, where $f$ satisfies the recurrence relation $f(n)=f(\frac{n}2)+1$ with $f(1)=1$

How can I proof this using regular induction and strong induction? $$f(2^k)=f(\frac{2^k}2)+1=f(2^{k-1})+1$$ $$f(2^{1-1})=f(2^0)=f(1)=1$$ $$f(2^{2-1})=f(2^1)=f(2)=f(1)+1=2$$ ...
3
votes
4answers
161 views

Solving the non-homogeneous recurrence relation: $g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$

$g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$ With initial conditions $g_{0} = 23, g_{1} = 37, g_{2} = 42 $ This is a practice question I'm working on, and I'm running into absurd amounts of ...
2
votes
5answers
680 views

Explanation of recursive function

Given is a function $f(n)$ with: $f(0) = 0$ $f(1) = 1$ $f(n) = 3f(n-1) + 2f(n-2)$ $\forall n≥2$ I was wondering if there's also a non-recursive way to describe the same function. WolframAlpha tells ...
2
votes
1answer
55 views

Find the generating function for a series , given a recurrence relation

I am solving a problem on an Online Judge. The problems solution boils down to find the solutions to the following recurrence relation: ...
-1
votes
1answer
34 views

Which is a linear and homogeneous recurrence?

Which of the following choices is a linear and homogenous recurrence? $1)$ $A_n = A_{n-1} + 4A_{n-2} + 3n$ $2)$ $A_n = n + 1$ $3)$ $A_n = (A_{n-1})^2$ $4)$ $A_n = 5A_{n-1} + A_{n-2} + 3A_{n-3}$
-2
votes
2answers
105 views

Using generation functions solve the following difference equation

Using generation functions solve the following difference equation $$ a_{n+1} - 3a_{n+2} + 2a_n = 7n ; n\geq0; a_0 = -1; a_1 = 3. $$
1
vote
2answers
80 views

Get the Nth term of a sequence 1,2,4,7,13,24…

I have a sequence: 1,2,4,7,13,24,44,81, ... and I think it's like a Fibonacci sequence, however you add three number together and not two ("Tribonacci"?). So: $$ v_n = v_{n-1} + v_{n-2} + v_{n-3} $$ ...
2
votes
2answers
50 views

Recurrence relation practice problem that I can't figure out

Thanks for taking the time to look at this problem. I'm trying to prepare for a test on Monday by doing some extra odd numbered problems from my textbook. I'm having a lot of trouble trying to solve ...
0
votes
2answers
48 views

Recurrence Relationship Questions

Consider the recurrence defined by: $$G_0 = 0\\ G_n = G_{n-1} + 2n - 1$$ Determine what Gn is for several values of n to determine a formula for Gn. $2n$ $n$ $2n-1$ $n^2$ *I believe this one is ...
1
vote
1answer
45 views

Simple Recurrence Questions [closed]

$r$ is a real number, define a recurrence relationship for $A_n$ $$A_0 = 1\\ A_n = r\cdot A_{n-1}$$ Question: What is the value of $A_4$ $4(A{n-1})$ $r^4$ $1$ $4r$ I've pretty much eliminated ...
0
votes
1answer
22 views

Find a sequence $a$ so that $a_n = s \Delta a_n $.

Let $s$ be a real number $ s \ne 0 $. Find a sequence $a$ so that $a_n = s \Delta a_n $ and $a_0 = 1$. Any help with this question will be great. This is my first time doing recurrence relations ...
0
votes
2answers
46 views

Two sequences $a$ and $b$ for which $\Delta a_n = \Delta b _n$

Find two different sequences $a$ and $b$ for which $\Delta a_n = \Delta b_n$ for all of $n$. This is my first time doing recurrence relations, so if anyone could provide some thorough and clear ...
0
votes
2answers
39 views

Solving a Linear Recurrence Relation

I made quick progress on this, and then of course got stumped, so here's the problem: $$a_0 = -1, a_1 = -2, a_n = 4a_{n-1} - 3a_{n-2}$$ So, following the way I was taught to solve this type of ...
3
votes
2answers
380 views

Linear Homogeneous Recurrence Relations and Inhomogenous Recurrence Relations

I'm having some difficulty understanding 'Linear Homogeneous Recurrence Relations' and 'Inhomogeneous Recurrence Relations', the notes that we've been given in our discrete mathematics class seem to ...
0
votes
2answers
32 views

How to get the characteristic equation from a recurrence relation of this form?

I've been getting the characteristic equation from relations of the form $$U_n=3U_{n-1}-U_{n-3}$$ Thanks to this question I made before: How to get the characteristic equation? Now, I recently ...
2
votes
3answers
52 views

How to Find Recurrence Relation?

I'd appreciate help in understanding how to approach/find a recurrence relation. For example, if we are given the following situation, how would one find a recurrence relation? A computer system ...
2
votes
5answers
91 views

How to find first five terms of sequence?

I'm new to recursion so please bear with me. I have to find the first five terms of a sequence with initial conditions $u_1 = 1$ and $u_2 = 5$, and, for $n \geq 3$, $$u_n = 5u_{n−1} − 6u_{n−2}.$$ I ...
0
votes
2answers
38 views

Solving for Recurrence Function

I was reading the following http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/99-recurrences.pdf notes on recurrence relation, page 2. A recurrence function for the Tower of Hanoi is given by ...
2
votes
1answer
70 views

Define a recursive sequence for the following formula f(n) = n(n+1)

Define a recursive sequence for the following formula f(n) = n(n+1). Preferably one only defined by previous $a_n$ terms, i.e., no 'n' terms. If possible that is. So for example the following ...
0
votes
2answers
30 views

Proofs by strong induction [duplicate]

I am trying to solve the following problem using strong induction, the problem is the following: For any positive integer $n$, let $T_n$ be the number $1$ if $n<4$ and the number $T_{n − 1} ...
0
votes
0answers
24 views

proving a recurrence relation

I'm trying to prove that the recurrence $T(n) = T(\alpha n)+T((1-\alpha)n)+n$, where $0<\alpha<\frac{1}{2}$, has an order of growth $T(n)= an$ log $n$ $\in \Theta(nlog(n))$ where $a$ is a ...
1
vote
0answers
33 views

Solve recurrence $a[n,k]=(2m-2k)\;a[n-1,k+1]+k\;a[n-1,k]$

I'm trying to count how many vectors of size $n$ there are, given that the elements of the vector are integers from the range $\{-m,m\}-\{0\}$ (zero is excluded), and there are no pair of elements ...
1
vote
2answers
41 views

Find a recurrence for in , the number of integer compositions of n which only have 1s and 2s as parts.

Find a recurrence for $$i_n$$ the number of integer compositions of $n$ which only have $1$s and $2$s as parts. How do you approach this problem?
0
votes
0answers
35 views

Finding general solution to a non-linear discrete time recurrence relation

I am faced to a non-linear discrete time reccurence relation and I can't find the general solution. The first question is: Is there a general recipe for finding the general solution to non-linear ...
3
votes
2answers
83 views

Is there a closed-form solution to this recurrence?

A friend and I were examining polynomials of the form $p_n (x) = x (x+1) (x+2) \cdots (x+n -1)$ and we were trying to come up with some kind of closed form for the coefficients when the polynomial is ...
0
votes
1answer
33 views

Finding the recurrence relation? [duplicate]

If I let $n \geq 1$ be an integer and use a $2 \times n$ board $D_n$ containing $2n$ cells, each side has a length of 1. T The brick can be vetical or horizontal containg $2$ cells(explained in the ...
0
votes
1answer
35 views

Solving a Recurrence Relation

In my research, I encountered the following recurrence relation: \begin{align} g(t) &= (\beta-1) \; g(t-1) + \beta \; f(t)\\ f(t) &=\min\{f(t-1)+g(t-1), \, c \cdot \lambda^t \} \end{align} ...