-1
votes
1answer
20 views

Inductive Proof Algorithm

so I'm working on an algorithms assignment and am having a tough time understanding what to do: The equation is: $$T(n) = 2T(n/4) + n = \Theta(n) = O(n)$$ Right now I have gotten this far: $$T(1) = ...
1
vote
1answer
46 views

How to prove a very basic algorithm by induction

I just studied proofs by induction on a math book here and everything is neat and funny: the general strategy is to assume the LHS to be true, and use it to prove the RHS (for the inductive step). Now ...
0
votes
1answer
74 views

How can I prove the correctness of this multiplication algorithm?

I want to know how I can prove that this algorithm is correct: ...
3
votes
1answer
36 views

Number of ways to color such that one color always leads

There are n boxes drawn out in a line. We have two colors, blue and red. We start coloring boxes from left to right. At any instant we want to color the boxes in such a way that number of boxes ...
0
votes
1answer
65 views

Proof by Induction Algorithm [closed]

I am stuck on trying to prove this algorithm using mathematical induction. ...
2
votes
0answers
49 views

Simple knapsack with arbitrary weights: Algorithm won't work, but my proof by induction doesn't agree.

We want to solve the simple knapsack problem: We're given a set of $n$ positive item weights, which are unique integers $\{w_1, \ldots , w_n\}$, and an integer $C > 0$, representing the capacity of ...
0
votes
0answers
25 views

Recurrence relation by expansion

I'm trying to find a general formula for the following recurrence relation: for n of the form 2^2^k S(n) = (rootn)(S(rootn))+n S(2) = 1 First, I let b = 2^2 just for readability ...
1
vote
2answers
46 views

$2^n-1 = \sum_{j<n}2^j$ induction explanation

I am having trouble understanding the following analysis after we arrived to the conclusion: $2^k - \sum_{j=0}^{j=k-1}2^j = 1$ after arriving to the conclusion, they say, I think to explain that the ...
1
vote
1answer
123 views

Proving by induction that a palindrome contains an even number of $b$s and $c$s

Suppose we want to construct palindromes that contain an $aa$ in the middle if the length is even and an $a$ in the middle if the length is odd. I'm trying to prove by induction that all of these ...
-2
votes
3answers
142 views

Horner Polynomial Evaluation: counting addition operations

We first note how the polynomial in Exercise 5 can be written in the nested multiplication method: ...
0
votes
5answers
138 views

Making sense of word problem

Suppose you begin with a pile of $n$ stones and split this pile into $n$ piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile ...
0
votes
0answers
99 views

max number of keys in a 2-3-4 tree

Let $M(L)$ be the largest number of keys (a $2$-node has $1$ key and two children, a $3$-node has $2$ keys and $3$ children, and a $4$-node has $3$ keys and $4$ children) in a $2-3-4$ tree that ...
0
votes
2answers
88 views

Showing that celling lg(n+1) = floor [lg n]+1

So im having a problem with the following: Show that $\lceil lg(x+1)\rceil = \lfloor lg x \rfloor +1$ for integers $x\ge 1$. I started to show it by proving by induction, only problem was after ...
0
votes
1answer
86 views

Recursive fibonacci algorithm correctnes? [proof by induction]

im studying for the computer science GRE, as an exercise i need to provide a recursive fibonacci algorithm and show its correctness by mathematical induction. here is my recursive version of ...
1
vote
1answer
121 views

Prove correctness for this lcm iterative program

Studying for finals, trying to solve this problem: Given positive integers $n$ and $m$, we say that $m$ is a multiple of $n$ iff there is some $k \in N$ such that $m = kn$. For positive ...
1
vote
1answer
167 views

Generalized Josephus problem

I have been reading generalized Josephus problem from Concrete Mathematics. The recurrence form for the problem is given as f(1) = a f(2n) = 2f(n) + b, for n >= 1 f(2n+1) = 2f(n) + y, for n >= 1 ...
2
votes
2answers
120 views

Recursive algorithm correctness: problem.

Considering that to prove a recursive algorithm we should refer to mathematical induction. Given the following algorithm (which sort an Array of size r) I found that base cases are for array size of 0 ...
1
vote
2answers
156 views

Prove that $n! ≥ (⌈n/2⌉)^{⌈n/2⌉}$ [closed]

Prove that : $n! ≥ (⌈n/2⌉)^{⌈n/2⌉}$
2
votes
1answer
88 views

Minimim steps required based on game logic

I have the following simple game logic. You start with G gold and 0 experience at Time = 0 minutes. There are different types of houses what you can build, each with his own properties. House A ...
0
votes
1answer
289 views

Using induction to show a greedy algorithm always makes the optimal task selection

Suppose we have a greedy algorithm like the following: ...
0
votes
2answers
277 views

How can induction be used to prove binary search is correct?

I'm having trouble understanding how to find an invariant to check if it's preserved, and generally how induction is used in proving the correctness of algorithms (binary search primarily, but others ...
2
votes
0answers
42 views

Proving a bound inequality for all n [duplicate]

Possible Duplicate: Prove that $\frac{n^n}{3^n} < n! < \frac{n^n}{2^n} $ for each $ n \geq 6 $ I want to prove $\dfrac{n^n}{3^n} \lt n! \lt \dfrac{n^n}{2^n}$ for all $n$ $\geq$ 6: So ...
2
votes
1answer
897 views

Induction proof of lower bound for $\sum \sqrt n$

I'm having some trouble proving the following statement using mathematical induction: $$\frac{1}{2}n^{\frac{3}{2}} \leq \sqrt{1} + \sqrt{2} + \sqrt{3} + \sqrt{4} + ... + \sqrt{n} ,\text{ (for ...
0
votes
1answer
346 views

Proving by induction

I'm having a problem relating to proving by induction that the Preorder(T) and Postorder(T) algorithms both print out all the nodes in the tree without repetition. I'm not quite sure where to start.. ...
1
vote
2answers
148 views

In mathematics, what is meant by induction?

I was going through MIT video lectures on "Introduction to Algorithms " . In order to solve recurrences by substitution the professor says that we can solve them by induction. What is actually the ...
-3
votes
1answer
120 views

Proving $T(n) \ge 2^{n/2}$, for all n, by induction

Trying to solve the following induction question, but I seem to be getting cold cause I am lost! Can someone help me, then point me in a direction I can relearn this stuff :) Wanted to prove: ...
3
votes
2answers
200 views

Can this be solved by induction? (number of ways of cutting a rod into pieces)

I am reading an algorithm example. The example is about Rod cutting. The idea is that a steel rod can either be sold as it is, or be cut into integral pieces and ...