Tagged Questions

1
vote
1answer
52 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 ...
1
vote
1answer
42 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 ...
0
votes
2answers
51 views

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

Prove that : $n! ≥ (⌈n/2⌉)^{⌈n/2⌉}$
2
votes
1answer
79 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
86 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
80 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
486 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
160 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.. ...
0
votes
2answers
133 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
118 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
139 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 ...