The tag has no wiki summary.

learn more… | top users | synonyms

-4
votes
1answer
37 views

Find a recursive algorithm to find $a^{2^n}$

Edit1: Used Latex. =] Edit2: Thanks for the guidance to the users below. Really helped me out editing the post and guidance on the math problem. The question gave me a hint: $a^{2^{n+1}} = (a^{2^n}) ...
-2
votes
0answers
32 views

Discrete Mathematics Recursion Question [on hold]

Function $f$ is defined recursively by $f(0)=f_0, f(1)=f_1$, and $f(n+2) = f(n)+f(n+1)$ for $n \geq 0$. (a) For $n \geq 0$, let $c(n)$ be the total number of additions for calculating $f(n)$ using ...
1
vote
2answers
64 views

Definition by Recursion: why is the existence part not (almost) obvious?

I saw the following statement. Let $H$ be a set, let $e\in H$ and let $k:H\rightarrow H$ be a function. Then there is a unique function $f:\mathbb{N}\rightarrow H$ such that $f(1)=e$, and that ...
4
votes
3answers
154 views

Definition of General Associativity for binary operations

Let's say we are talking about addition defined in the real numbers. Then, by induction we define $\sum_{i=0}^{0}a_i=a_0$ and $\sum_{i=0}^{n}a_i=\sum_{i=0}^{n-1}a_i+a_n$ for $n> 1.\:$ Now, how do ...
0
votes
0answers
56 views

Kleene's recursion theorem

Would anybody be able to provide me (someone with little familiarity with the subject matter) with a bit of background to the Recursion Theorem and guide me towards some texts on its mathematical and ...
0
votes
0answers
127 views

Differend kind of recursion.

How are called these special case of definition by recursion? given increasing $f,g: \Bbb {N} \rightarrow \Bbb N$ and $b,b_1,b_2 \in \Bbb N$ 1 (a special case of primitive recursion) ...
4
votes
0answers
147 views

General overview about Recursion (free online texts)

I'm looking for free online texts about recursion. What I'm looking for formal definitions* of "all" (most of) the different types of recursion and from different points of views like Category ...
1
vote
1answer
19 views

How to find a pattern in this recursive sequence algorithmically?

I'm trying to find the closed-form of a sequence algorithmically. Here is the recursive sequence: $$w_k=w_{k-2}+k, \forall k \in \Bbb{Z} | k \geq 3, w_1=1, w_2=2$$ which produces this sequence: ...
2
votes
2answers
25 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 ...
1
vote
3answers
92 views

Recurrence relations (Big-O notation)

Say I'm given a recursive function such as: function(n) { if (n <= 1) return; int i; for(i = 0; i < n; i++) { function(0.8n) } } ...
3
votes
4answers
40 views

Is this a correct recursive sequence definition?

Take this definition: Is this definition of $s_k$ for $k\ge2$ correct? $s_k=6a_{k-1}-5a_{k-2}$ but where does the $a$ term come from? The book swaps $a$ and $s$ interchangeably.
0
votes
2answers
42 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 ...
0
votes
2answers
13 views

Recursion, Explicit Equasion

Prove $\ a_{n}<2^{n} $ for every natural number n, where $\ a_{n} $ is defined recursively by $$ a_{1}=1, a_{2}=2, a_{3}=3, a_{n}=a_{n-3}+a_{n-2}+a_{n-1},\ for\ n>=4$$ Once I get the explicit ...
1
vote
1answer
40 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
27 views

Recursively defined sequences

So, this question has been giving me a little bit of trouble. It's supposed to be just a few lines, and I know that I don't need to write out the base case, recursive step, and restriction. I ...
1
vote
0answers
31 views

A Problem about Recursion

Consider recursion $$a_n+c_1a_{n-1}+\cdots+c_ma_{n-m}=0~~~~~~~~~~(1)$$ Let $\lambda^m+c_1\lambda^{m-1}+\cdots+c_m=0$ be the characteristic function and $(\lambda_1,n_1),\cdots,(\lambda_s,n_s)$ be ...
2
votes
1answer
52 views

Guess an explicit formula for recursively defined sequence

Was given this as a question. "Use iteration to guess an explicit formula for the recursively defined sequence and then prove that the formula is a solution to the recurrence using induction: ...
0
votes
1answer
18 views

Prove uniqueness of recursive function

I am currently reading Cutland's Computability and would like to figure out how to solve Theorem 4.2 which states: Let $x=(x_1 \dotsc x_n)$, and suppose that $f(x)$ and $g(x,y,z)$ are functions; ...
0
votes
1answer
17 views

how to write a recursive definition

so the question asks to define s(n) as the number of strings of a's b's and c's of length n that do not contains "aa". write a recursive definition for s(n). what is s(0),s(1),s(2),s(3). i had to ...
0
votes
1answer
24 views

How to deduce from a recursive variant of the triangular numbers the non-recursive form?

This is probably simple (if not, my apologies beforehand), but I have the following formula: $$f(0) = 2$$ $$f(x) = 6x + 2 + f(x -1) \; \text{ where } x \in \mathbb{N}_{\gt 0}$$ The formula actually ...
2
votes
0answers
59 views

Ackermann function is not primitive recursive

The function of the Ackermann function is defined as $$ A_{0}(y)= y+1$$ $$ A_{x+1}(0)= A_{x}(1)$$ $$ A_{x+1}(y +1)= A_{x}(A_{x+1}(y))$$ I want to show that the function of ackermann is primitive ...
0
votes
1answer
25 views

proof using a recursive definition

I am doing a 2-part question. Thus far, I have finished the first part, requiring me to make a recursive definition of a set "S" of all binary strings, starting with a 1. I have: Base: 1 Recursion: ...
0
votes
0answers
16 views

Structural induction question?

The question is: Give recursive definition of a set "S" of all binary strings starting with a 1. Do the three steps: base, recursion, and restriction So far, I have: base: empty string recursion: ...
2
votes
0answers
99 views

Repertoire method for solving recursions

I am trying to solve this four parameter recurrence from exercise 1.16 in Concrete Mathematics: $g(1) = \alpha;$ $g(2n+j) = 3g(n) + γn + β_j$ : j = 0,1 and n >= 1 I have assumed the closed form to ...
-1
votes
1answer
49 views

Proof of a sequence with recursion

The problem asks to prove the following to be true. $$F^2_{n+1} - F_{n+1} F_n - F_n^2 = (-1)^n$$ Anyway, I've tried looking at this or similar proofs for going on an hour now, pretty much the only ...
1
vote
2answers
21 views

Question over recursive definitions

Let $E$ be the set of even integers. Then the Base Case: $0\in E$ And the constructor case would be If $n \in E$ then so are $n+2$ and $-n$. This makes sense. But would the Base case and constructor ...
-1
votes
0answers
29 views

How To Solve the recursion?

Need help with the following recursion: $$T(n)=2T\left(\frac n2\right)+ \frac n{\log n} $$ I Tried to solve it to no avail, and the master theorem doesn't seem to work on it. Thanks
2
votes
5answers
59 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 ...
3
votes
2answers
40 views

$T(n)=T(cn) + T((1-c)n)+1$ while $0<c<1$

Question: $T(n)=T(cn) + T((1-c)n)+1$ $0<c<1$ and $T(1)$ is constant. My thoughts: I'm trying to solve this recursion using Induction, but I think I got it all wrong. My guess is that $T(n) = ...
3
votes
1answer
100 views

Solve Recurrence Equation with Induction

Question: Given the recurrence equation for the recursive Fibonacci sequence program: $T(n) = T(n-1) + T(n-2) + b$ $T(0) = T(1) = a$ Using induction, show that $T(n) \leq f(n)$, where $f(n) = c2^n, ...
12
votes
4answers
423 views

Find all bijections $\,\,f:[0,1]\rightarrow[0,1]\,$ satisfying $\,\,f\big(2x-f(x)\big)=x$.

A friend of mine gave me the following problem: Find all functions $f:[0,1]\to[0,1]$, which are one-to-one and onto and satisfy the functional relation $$ f\big(2x-f(x)\big)=x, \tag{1} $$ for all ...
0
votes
1answer
40 views

Is there a recursive formula for Euler's Totient function

I have been looking for a recursive formula for Euler's totient function or Möbius' mu function to use these relations and try to create a generating function for these arithmetic functions.
0
votes
1answer
29 views

Discrete Math Recursive Functions for Strings

Recursive Functions for Strings Construct a recursive definition for the following string function over the alphabet {x,y}: f(x) returns the string where every x is replaced by xy and every y is ...
1
vote
1answer
154 views

Survival Probability of a Population

A population starts with one amoeba. In each generation, each amoeba divides in two with probability $\frac{1}{2}$, or dies, with probability $\frac{1}{2}$. Let $p_n$ be the probability that the ...
0
votes
0answers
23 views

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity if we have 3 rods. So for example disk 2 can't be placed on disk 4, or disk 1 can't ...
0
votes
2answers
48 views

Prove via induction this recursively defined sequence

Let $P(n) = 2P(n-1) + n, P(1) = 3.$ Use induction to show that $$P(n) = 3(2^n) - n - 2$$ Highly verbose solutions are greatly appreciated.
2
votes
1answer
116 views

How to solve this recurrence relation with Sigma notation (f(n, m) = f(n - 1, m) + f(n, m- 1) + c?

This recurrence relation was inferred from the function $f(n, m) = f(n - 1, m) + f(n, m-1) + c$. After expanding the latter, I ended up with the following: $$f(n,m)=\begin{cases} 0,&\text{if ...
12
votes
1answer
158 views

The problem of the most visited point.

Represents the set $R_{n\times n}=\{1,2,\ldots, n\}\times\{1,2,\ldots, n\} $ as a rectangle of $n$ by $n$ as points in the figures below for exemples. How to calculate the number of circuits that ...
1
vote
2answers
92 views

Convergence and limit of a recursive sequence

Let $p>0$ and suppose that the sequence $\{x_n\}$ is defined recursive as $$ x_1 = \sqrt{p}, \quad x_{n+1} = \sqrt{p + x_n}, $$ for all $n \in \mathbb{N}$. How can I show that $x_n$ converges, ...
0
votes
1answer
28 views

Show that the set of sets {$A_n$} has $n$ elements and that it is transitive

We define by recursion the set of sets {$A_n : n∈ℕ$} this way: $A_0 = ∅$ $A_{n+1} = A_n ∪$ {$A_n$}. I want to prove by induction that for all $n∈ℕ$, the set $A_n$ has $n$ elements and that $A_n$ ...
0
votes
2answers
81 views

Prove that a Fibonacci number is greater than $ φ^n$

How can I prove the following: If $f_n$ is a number of the Fibonacci sequence and φ= $\frac{1+\sqrt{5}}2$, then $f_n > φ^n$ for every $n >2$? I have tried using induction but I can't ...
0
votes
2answers
29 views

What is the general stragety for conjecturing a formula based off a pattern?

Is it simply to guess and evolve a answer until it gets closer or is there an approach? Ex: Find the formula for: $a_k = \frac{a_{k-1}}{2} + 1$ where $a_0 = 1$. One would go: $a_1 = 3/2, a_2 = ...
0
votes
1answer
19 views

How do you use induction on a recursive sequence using different variables?

I've been working on some recursive sequences for my Discrete class. I've understood most of them, but I've come to a new question which I'm confused about. A sequence $C_{0}$, $C_{1}$, $C_{2}$ is ...
3
votes
0answers
51 views

Induction on Primitive Recursive Function

The set $F_{n}$ of primitive recursive function symbols of arity $n$ can be defined inductively as: \begin{align} & Z, \text{Succ} \in F_{1} & \\ &\pi_{j}^{n} \in F_{n} \quad \text{for ...
0
votes
3answers
30 views

Figuring out the steps in a Recursive Function

I have the following recursive function: $f(0) = 7$ $f(n+1) = f(n) + 6n + 1$ for all integers $n => 0 $ I know the answer is $f(n) = 3n^2 + 2n + 7$ I would like to know the steps to get to this ...
5
votes
1answer
65 views

Eigenvalues appear when the dimension of the Prime Index Matrix is a prime-th prime. Why?

I had a look at the eigenvalues of the matrix, I called it Prime Index Matrix (is there a better name?), constructed like the following: $$ P_{k,p_k}=P_{p_k,k}=1, $$ where $p_k$ is the $k$th prime. ...
2
votes
0answers
55 views

Find the sum of exponentails of squares $\sum_{r=1}^n e^{-\alpha r^2}$

I would like to find $$a_n =\sum_{r=1}^n e^{-\alpha r^2},\qquad \alpha\in\mathbb{R}$$ I tried to solve the equivalent recursion $$a_n=a_{n-1}+e^{-\alpha n^2}\quad(n>0),\qquad a_0=0.$$ with an ...
1
vote
0answers
21 views

recursive definition produces different sequence than non-recursive

I had a homework problem where I had to give a recursive definition for the sequence $$a_n = n(n+1)$$ Which produces {2, 6, 12...}, so I first came up with this (I'll call it answer 1): $$a_{n+1} ...
1
vote
0answers
62 views

How to get the period of oeis.org/A130166 other than by trail?

oeis.org/A130166 a(0)=1; a(n)=prime(mod(a(n-1),1000)) starts with: ...
3
votes
1answer
56 views

Recursively deleting every second element in a list

This question got me thinking. If you have a list of length n and recursively delete every other element from the list until only one element remains, is there any ...