The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
2answers
101 views

Basic Discrete Mathematics Question

I was preparing my self before an exam and I found this question: For each of the following equations, find a positive integer $n$ that satisfies the equation. The notation $p(n,r)$ stands for ...
0
votes
1answer
69 views

Surjection, Recursion and Induction

Let $S$ be the set inductively defined by: 1) $* \in S$ 2) If $a \in S$ and $b \in S$ then $\langle a,b \rangle \in S$. For each natural number $n \in \mathbf{N}$, let $d(n)=\text{max}\{k ...
2
votes
2answers
323 views

Induction and Recursion: $f(1)=2$ and $f(n)=f(n-1)+2n$ for $n>1$

I have bad time with induction and recursion and I have an exam soon. We have this: $$f(1)=2$$ $$∀n>1:f(n)=f(n-1)+2n$$ We need to proof that is the solution of f(n)=f(n-1)+2n,f(1)=2 is: (the ...
1
vote
1answer
116 views

Principle of recursion for inductively defined relations

If we consider a relation $R$ and then its symmetric-reflexive-transitive closure --say $R^*$--, is there a recursion principle associated with $R^*$? It seems to me that such unique function is not ...
0
votes
0answers
20 views

Recursion questions - How much series from $A=\{\dots\}$ have that which satisfy the conditions

I am trying to solve recursions problems to understand "how its works" and faced in 2 questions: How much series from $\{1,2\}$ have that the sum of the terms is $n$ How much series from $\{0,1,2\}$ ...
1
vote
1answer
57 views

Recursion Master Theorem

I know that the master theorem states that if $n=d^k$: $$ T(n) = CT(n/d) + f(n)\text{ for }k >= 1\text{ and }T(1)= 1 $$ then $$ T(n)=\sum_{j= 0}^k C^j f(n/d^j) $$ Then how do I get $T(n) = k+1$ ...
1
vote
2answers
388 views

Can't understand a recursive definition of concatenation of two strings

I'm reading Rosen's Discrete Mathematics and its applications(6ed), but I can't understand a recursive definition about concatenation of two strings: Two strings can be combined via the operation ...
1
vote
1answer
54 views

Need help with proving the recursion

Let $p_{k}(n)$ indicate the number of partitions of n into k parts. Prove: $$p_{k}(n) = p_{k-1}(n-1) + p_{k}(n-k)$$ Example: There are two partitions of $5$ into three parts. $5 = 3+1+1$ $5 = ...
1
vote
2answers
38 views

First Order Recursion

Well I got this problem: $$T(0) = 0$$ $$T(n) = 3T(n/2) + n, n \geq 1$$ I simplified the equation to the following. $$3^iT(n/2^i) + 2n((3/2)^i - 1)$$ From this point I am confused how to solve. ...
0
votes
2answers
66 views

Asymptotic bounds of $T(n) = T(n/2) + T(n/4) + T(n/8) + n$

This problem is given in "Introduction to Algorithms", by Thomas H. Cormen. I have the answer to it, but I don't understand it. The answer is, $T(n) = \Theta(n)$. It would be really good if you ...
1
vote
0answers
84 views

Maximizing a continuous recursive function

So I've been working at this for a while and have so far been unable to find any resources on maximizing a particularly strange function that I've been trying to deal with. The function is of the form ...
1
vote
1answer
46 views

How many chess games are required to be played if 9 players win 2 games against each other player?

How many chess games are required to be played if 9 players win 2 games against each other player? Would the answer = 1152? I got this because each player plays 8 games in 1 iteration (he cannot ...
1
vote
1answer
65 views

Is this recursion well-defined?

I have a recursion defined by $$ f(n)=\max\{0,-c+pf(n-1)+(1-p)f(n+1)\} $$ with $0.5<p \leq 1$ and $f(0)=R>0$ and $f(m)=0$ for some $m>0$. I am trying to show that $f(n)$ is decreasing in ...
2
votes
2answers
117 views

recurrence relation homework question

This is a homework question let $a_n$ number of n digit quaternary $(0,1,2,3)$ sequences in which there is never a$ 0 $anywhere to the right of a $3$. Solve for $a_n$ bot sure how to go about this. ...
2
votes
1answer
88 views

Algorithm analysis

Consider a recursive Mergesort implementation that calls Insertion Sort on sublists smaller than some threshold. If there are n calls to Mergesort, how many calls will there be to Insertion Sort? ...
2
votes
2answers
101 views

Purchasing Order: An Analysis on A ($\textrm{C++}$)-Approached Recurrence Relation

Suppose that we have $n$ dollars and that each day we buy either tape at a dollar, paper at a dollar, pens at two dollars, pencils at two dollars, or binders at three dollars. If $R_n$ is the number ...
1
vote
1answer
77 views

Orange Juice, Milk, or Beer

Suppose that we have $n$ dollars and that each day we buy either orange juice for a dollar, milk for two dollars, or beer for two dollars. If $R_n$ is the number of ways of spending all the money, ...
0
votes
1answer
82 views

Recursive function diagram and transformed into a non-recursive function?

I have to parts to my questions and I am a beginner at programming. Im not sure how to translate a code into a diagram. Draw a diagram illustrating the values as the function is called… and the ...
0
votes
3answers
147 views

(CHECK) $n$-bit Strings Containing a Pattern

$$\text{$\bf{PLEASE~~~CHECK~~~AUTHOR'S~~~ANSWER}$}$$ If $S_n$ denotes the number of $n$-bit strings that do not contain the pattern $00$, then what is the underlying recurrence relation and ...
1
vote
1answer
46 views

Bit strings, $\omega$, $\lambda$ - need help interpreting and describing

Problem For these recursive definitions of sets of bit strings, show 5 elements from each set, and identify what set it is (in a few words). Attempt 1 Basis: $1 \in S_!$ Recursion: $\omega \in ...
2
votes
0answers
56 views

Acceptable numbering of partial computable functions required to be one variable?

Soare in a yet unpublished textbook (I happened to be in a class taught by one of his former graduate students where we were field-testing a rough draft of his new textbook) Computability Theory and ...
2
votes
1answer
64 views

Solve a recursion using generating functions?

Given the recursive equation : $$F_n+F_{n-1}+⋯+F_0=3^n , n\geq0$$ A fast solution that I can think of is placing $n-1$ instead of $n$ , and then we'll get : $$F_{n-1}+F_{n-2}+⋯+F_0=3^{n-1} $$ ...
4
votes
1answer
68 views

Number of times $g(p_1)$ occurs in $\sum_{d\mid n}g(d)$

$$ g(n)=\begin{cases} 1 & \text{if }n=1 \\[10pt] \sum_{d\mid n,\ d\ne n} g(d) & \text{else} \end{cases} $$ How can I calculate $g(n)$ efficiently? I was trying to collect all the $g(p)$ ...
2
votes
1answer
67 views

constructive proof of solution for this recursive formula

The two conditions $$\frac{p_{\mathrm{up}}(n)}{p_{\mathrm{down}}(n+1)}=c \quad \text{and} \quad p_{\mathrm{up}}(n)+p_{\mathrm{down}}(n)=1$$ lead to $p_{\mathrm{up}}=\frac{c}{c+1}$ and ...
2
votes
0answers
77 views

Prove that $\{(x,y): W_x\text{ and }W_y\text{ are recursively separable}\}$ is $\Sigma_3$-complete

Prove that $\{(x,y): W_x\text{ and }W_y\text{ are recursively separable}\}$ is $\Sigma_3$-complete This is a question from Soare's Recursively Enumerable Sets and Degrees. I have little idea how ...
3
votes
1answer
60 views

Recursively Defined Entities

So I am having some trouble understanding how one is to come up with the recursive definition to the following problem... We are given a rectangle of width $2$ and length $n$. Suppose we have ...
1
vote
3answers
79 views

Recursion Question - Trying to understand the concept

Just trying to grasp this concept and was hoping someone could help me a bit. I am taking a discrete math class. Can someone please explain this equation to me a bit? $f(0) = 3$ $f(n+1) = 2f(n) + ...
0
votes
1answer
199 views

$n$ Lines in the Plane

How am I to "[u]se induction to show that $n$ straight lines in the plane divide the plane into $\frac{n^2+n+2}{2}$ regions"? It is assumed here that no two lines are parallel and that no three lines ...
0
votes
0answers
58 views

How would you find a closed form expression for the following:

$$a_n = \frac{n}{n+1}a_{n-1} + \frac{n}{n-2}a_{n-2}\;,\;\;n\ge 3\; $$ For: $ 0 \leq n \leq 2 $, $a_n= n $
1
vote
2answers
29 views

what is the explicit form of this iterativ formular

I am not sure, if there is an explicit form, but if there is, how do I get it? This is the formula: $$c_n=\frac{1-n \cdot c_{n-1}}{\lambda}$$ where $\lambda \in \mathbb{R}$ and $n \in \mathbb{N}$ I ...
1
vote
1answer
60 views

Determining the effective tax rate in a tax on tax situation

There are taxation situations where the taxable amount includes the tax calculated on the taxable amount (e.g. this is a recursive calculation, as follows)... ...
1
vote
2answers
59 views

Recursion problem help

The following are the teachers example problems. The issue is that I don't understand the exact steps they took to go from $f(0)$ to $f(1)$ to $f(2)$ to $f(3)$. What I'm asking here is if someone ...
4
votes
2answers
79 views

Alternative unconditional form of $\sqrt{n -\sqrt{n -\sqrt{n -\cdots}}}$?

Consider $a_n$, where $$\begin{align} a_n &=\small{\sqrt{n -\!\!\!\sqrt{n -\!\!\!\sqrt{n -\!\!\sqrt{n -\!\!\sqrt{n -\!\!\sqrt{n -\!\sqrt{n - \cdots}}}}}}}}\end{align}$$ Using a recursive ...
3
votes
2answers
121 views

How do we know that every halting Turing Machine can be expressed as a recursive function?

I've hear many times that a major result in Recursion Theory is the equivalence of Turing and Godel's models: the functions implementable on a Turing machine are precisely the functions that can be ...
3
votes
1answer
86 views

Help with generating functions.

Background. Let $P_0(y)=2y-3$ and define recursively $$P_{n+1}(y)=4y\cdot P_n'(y)+(5-4y)\cdot P_n(y).$$ I would like to know as many properties of $P_n$ as I can. For example, it can be shown that ...
1
vote
1answer
30 views

Recursive String Proof

Have I done this right? I have shown that every element of Σ exists in Σ*, so is it ok to do what I did in step 5? ...
1
vote
1answer
48 views

Recursive algorithm

I am trying to understand how this works. My instructor is teaching his first class, in summer on top of that, and only had 3 slides on this and had to rush over it. His example is: ...
4
votes
2answers
64 views

Probability (usage of recursion)

In an hour, a bacterium dies with probability $p$ or else splits into two. What is the probability that a single bacterium produces a population that will never become extinct?
0
votes
0answers
148 views

random sample algorithm with m subsets

Suppose we want to create a random sample of the set {1, 2, 3, ... n}, that is, an m-element subset S, where $0 \leq m \leq n$, such that each m-subset is equally likely to be created. One way ...
2
votes
2answers
50 views

Using polynomials as recursions

I made this observation in my discrete math course a while back. I explored it further online, so not all the ideas contained are mine alone. I still am confused about some things, though. Consider ...
0
votes
0answers
67 views

recursion for paths in binary tree

I have a binary tree, with {a,b,c} nodes and {p,q} edges. When $ p + q = 1 $. the first tree a - p - b - q - c this generate the expresion $ bq + cq $ ...
0
votes
3answers
263 views

Calculating loan + interest recursively

I am trying to calculate a loan amount where the total principle depends on the payment amount. Here's a simple example, leaving aside that a) no bank would actually do this, and b) my income is not ...
2
votes
1answer
343 views

2T(n/2) +n by induction

I try to proof by induction that: $$ T(n)= 2 T(n/2)+n \quad n>2,\quad T(2)=2,\quad n = 2^{k}$$ is $$ n*lg_2(n) $$ How can I do this? Thanks Steps that i went throw: ==Base Case== $$T(2) = 2, ...
1
vote
3answers
51 views

Solve recurrence equation

Could you Show me how to solve this equation: $$x_n = \sqrt2x_{n-1} + \sqrt3$$ for $n \ge 1$ with $x_0 = 1$.
2
votes
1answer
84 views

Identity involving a recursive product

Here is yet another problem related to plane partitions. Given the recursive formula $$ \begin{align*} F(0)&=1,\\ F(r)&=\prod_{i=1}^r\frac{i+2r-1}{2i+r-2}F(r-1). \end{align*} $$ How can we ...
3
votes
1answer
117 views

Are hyperoperators primitive recursive?

I apologize if this question is too basic. I have read that the Ackerman function is the first example of a computable but NOT primitive recursive function. Hyperoperators seem to be closely related ...
1
vote
0answers
47 views

Reasoning about a recursive function

First of all, I am a computer science student, not a maths student. So maybe this is a trivial question, I just would like to understand it :) Suppose I have the following (pointless) recursive ...
1
vote
1answer
72 views

Solving Recursions like this

How can i solve this equation? I am really stuck $T(n) = T(n + 1) + T(n + 2) + 3n + 1$ $T(0)=2$ $T(1)=3$
0
votes
1answer
112 views

Recursive Definitions with Converse

I think I know how to solve i. and ii., but not iii: Base Case: $(0,0) \in S$ Recursive Step: If $(a,b)\in S$, then $(a+1,b+2)\in S$ and $(a+2, b+1)\in S$. (For i and ii): Prove that if $(a,b) \in ...
1
vote
2answers
68 views

Simple recursive equation sub-solution.

I have tried to solve a very simple recursive equation:))), but I don't know what's wrong with my brain but I got other solution when I partially solve the equation. Equation: $$T(n) = (n+2) + ...