That was an exact answer I was looking for. I thought along those
lines, But not sure whether its right.... Thanks....
On Jun 13, 5:44 am, ross <jagadish1...@gmail.com> wrote:
> @howtechstuffworks:
>
> Your question seems to be - why 'k+1' and not 'k+2' or 'k+3' or
> something else.
> The simple reason is that,
>
> Given that P('k') and P('k+1') is true, we can extend it for ANY value
> of k.
> (ie) k+2 , can be derived from 'k+1' by substituting k=k+1.
> similarly k+3 can be derived from 'K+1' by substituting k=k+1
> twice..
>
> The reason thus is that, there ANY INTEGER can be expressed in terms
> of its consecutive integer (consecutive - differ by ONE). that is why
> k+ 'ONE' is chosen for proving so that the induction works for all
> numbers.
>
> (Assuming u prove for P(k+2) as true as in your claim, you cannot
> derive P(k+1) as true from these statements by substituting k=k+2..
> And if your prove truth for P(2k) as claimed by you, then numbers
> which are NOT even, cannot be expressed in the form 2k by substituting
> int value for k.)
> If you prove P(3k), then numbers which are NOT multiples of 3 cannot
> be expressed in the form 3k by substituting integer value for k)
>
> so, k+1 becomes the natural choice so that all possible values greater
> than the base case are considered. Hope that helps.
>
> On Jun 13, 9:29 am, HowTechStuffWorks <howtechstuffwo...@gmail.com>
> wrote:
>
>
>
>
>
>
>
> > Thanks, Gene. That was an very thoughtful example. I have one more
> > doubt like, what we are trying to prove here. That the example will
> > work for all numbers(all natural numbers, not only for an multiple of
> > two or three or some number) or this example will work for all
> > possible(infinite) numbers.
>
> > Regarding the Trees problem, since the initial value is one and all
> > the tree down will have an even number of child say 2^i till the leaf.
> > Isn't it possible to prove based on the theorm, that an odd number +
> > even number is always an odd number. Also we can reduce it to the form
> > that number of elements is given by the formula, (2^k-1). 2^anything =
> > even; even-1 = odd;
>
> > If I do by mathematical Induction,
>
> > base case : k = 1; value = 1;
>
> > kth step : kth step (2^k-1)
> > k+1th step : (2^k+1)-1 => (2^k.2)-1; //////////// what are we
> > proving here? and how are we verifying it????
>
> > When I tried to apply some numbers for the value, I came across this
> > thought.
> > k = 0; value = 1
> > k = 3; Value = 8
> > k+1 = 4 Value = 16 => this can be derived from (2^k+1)-1 => (2^k .
> > 2^1)-1 => (8.2) -1 => 15
>
> > But I am not sure how to proceed with the abstract inductive step and
> > I am not sure what we are trying to prove.
>
> > Also why we always want to prove the k+1 th step??? why not k+2th or K
> > +i th step????
>
> > Also can you give me some example where the induction fails.
>
> > Thank you very much.
>
> > On Jun 12, 11:15 pm, Gene <gene.ress...@gmail.com> wrote:
>
> > > Suppose you want to prove that you can climb all the way to the top of a
> > > ladder. One way to do this is in two parts: First prove you can stand on
> > > the bottom step. Call this step 1 and number the rest of the steps
> > > 2,3,..N
> > > upward to the top of the ladder.
>
> > > The second part is to prove that if you are on any step K, you know how to
> > > take one step upward to step K+1. (I'm not telling you how to do that
> > > here.
> > > But suppose you know how.) This is called the "inductive step." (Pun
> > > intended.)
>
> > > The principle of indication is that these two proof parts taken together
> > > provide the desired proof.
>
> > > In this case, the proof is constructive. (This isn't always true.) You
> > > effectively get an algorithm for climbing the ladder as a byproduct of
> > > proof: Stand on the first step 1. Now use the inductive step with K=1 to
> > > get to step K+1 = 2. Use it again with K=2 to get to K+1=3. Continue
> > > using
> > > N-1 times. This puts you at the top of the ladder.
>
> > > Note that in computer science you often need more complex kinds of
> > > induction
> > > - for example over data structures - rather than integers. For a simple
> > > example, take induction over trees. Prove that complete binary trees
> > > (where
> > > all nodes are either leaves or have 2 children) always have an odd total
> > > number of nodes.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
