All Questions
Tagged with recursive-algorithms induction
51
questions
0
votes
1
answer
39
views
How to Prove Division of One Bezier Curve into Two using de Casteljau Algorithm
$\newcommand{\brstbasis}[2]{b^{#1}_{#2}}$
$\newcommand{\posintset}{\mathbb{Z}^{+}}$
$\newcommand{\intset}{\mathbb{Z}}$
$\newcommand{\realset}{\mathbb{R}}$
$\newcommand{\domain}[1]{\operatorname{dom}\...
- 1,840
0
votes
0
answers
28
views
Understanding base cases of inductive proofs in algorithm analysis Cormen et al
I am currently working through Cormen et al's classic book on algorithms and data structures. I am trying to follow an inductive substitution proof that the following time complexity function is $O(n\...
- 496
0
votes
0
answers
61
views
Mathematical Induction to Prove Binary Search for First Occurrence of an Element in a Sorted Array
$\newcommand{\cardinal}[1]{\abs{#1}}$
$\newcommand{\cardinal}[1]{\abs{#1}}$
$\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}$
$\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}$
$\...
- 1,840
1
vote
1
answer
88
views
How do I write the induction hypothesis when dealing with recursive formulas
The sequence $ \{a_n\}_{n=0}^{\infty} $ is recursively defined by $ a_0 = 0 $, $a_1 = 1 $, $a_2 = 4 $ and
$a_n = a_{n-1} + a_{n-3} - n^2 + 8n - 10$
for $ n \geq 3 $.
Prove using induction or strong ...
- 35
0
votes
1
answer
63
views
How was the solution to this recurrence obtained?
I am trying to understand the solution to the following recurrence.
$I(n) = 1+n/B$ if $n \leq \alpha M$ and $I(n) = 4I(n/2)+1$ otherwise.
The solution, according to the paper this is from, is $I(n) = ...
- 1,279
0
votes
1
answer
69
views
Find the explicit formula for this recurrence relation [closed]
Solve this recurrence relation:
$$a_0 = 1$$
$$a_n = 2^{2(5-n)+1}* a_{n-1} + 1$$
We've only covered linear homogeneous recurrence relation in our course so I'm a little lost and any help would be ...
- 51
0
votes
1
answer
103
views
1
vote
2
answers
494
views
Recurrence equation for $T(n)=T(n-1)+cn$ by substitution (induction)
I was able to solve this relation as described here
Solving the recurrence relation $T(n)=T(n-1)+cn$
By the way, my exercises asks also to demostrate by "substitution" and "induction&...
- 197
1
vote
2
answers
80
views
Prove $T(n) = T(\lfloor n/2 \rfloor) * T(\lfloor n/2 \rfloor) \leq 2^n$
I am stuck on the below problem.
Here is what I have so far, and I have highlighted the area that I am not understanding, particularly in the induction step when we start evaluating for k+1.
$T(n) = T(...
- 11
-1
votes
1
answer
74
views
Inductive proof for recursive function
Let $\Sigma$ denote an alphabet and $[ \Sigma ]$ set of lists over the alphabet.
I've encountered the following function:
$f([])=[]$
$f([x])=[x]$, for $x \in \Sigma$
$f(x:L)=f(L)$, for $x \in \Sigma$ ...
- 9
1
vote
1
answer
531
views
Proof by Induction on a recursive function
its been a while since I have done proofs and am struggling on a question:
Let $T(n)$ be defined recursively as follows: $T(1)=c$ and $T(n)=3T(n/3)+c, \forall n\geqslant 3$, where $c$ is some ...
- 133
1
vote
1
answer
42
views
Proof of closed-form expression for a recursive formula by induction
With $f:\mathbb{N}\rightarrow\mathbb{R}_+$ and
$$T(1)=b$$
$$T(n)=a*T\left(\frac{n}{c}\right)+f(n)$$
for
$$a,b,c>0$$
$$n>1$$
Prove by induction that
$$T(n)=\sum_{i=0}^k \left(a^i * f\left(\frac{n}...
2
votes
1
answer
414
views
Proof by induction - algorithm
I need some help to sort out if my answer is right for this question. The algorithm calculates $x^n$.
Question: Argue the correctness of the algorithm using proof by induction.
Note: Even if you haven'...
- 27
0
votes
1
answer
83
views
Tips for a recursive function, proof by induction
Suppose the following
$$ f(0)= 0$$
$$ f(1)=2$$
$$ f(n)= 4f(n-1)-3f(n-2)$$
I want to prove that
$$f(n)= 3^n -1$$
by induction.
I started by trying this
$$f(n+1)=4f(n)-3f(n-1)$$
Which gives me this:
$$ ...
0
votes
2
answers
70
views
Can somebody help me with this mathematical induction proof? [closed]
It's a recursive equation and I'm not sure how to demonstrate it through mathematical induction.
- 15