Assistance w/ Inductive Proofs required :-)

[finkeljo]

Hey all, I got a proposition I am supposed to prove by induction but am just a bit confused. The problem is as follows:

Prove by the principle of mathematical induction that if m is a natural number, then for each natural number n, there exists an integer a greater or equal to zero such that,

n*2^m <= (n+a)*2^m

The inequality is not that difficult but I am just unsure as to which variable I would be doing the induction on. I assume its n, since the proposition is making a statement for all n. Any thoughts otherwise?

And additionally if I did do induction on n, how would I then show existence for a??

Thanks for the help.

 

[hunt_mat]

It says for each n, so n is the variable you use induction on.
First off take n=1, what does the theorem state then?, is the inequality you're trying to solve the following:
$$n\cdot 2^{m}\leqslant (n+a)2^{m}\Rightarrow n\leqslant n+a$$
Is this not obvious, have you copied the question down correctly?

Mat

 

[finkeljo]

Thanks for your replay Mat. No that is the question,, my teacher is concerned with our actual writing of the proofs more so than giving us tuff problems. And yes lol it is incredibly obvious but how do i state it mathematically? arrgghh!

 

[Mark44]

1. Establish a base case (typically for n = 1).
2. Assume that the statement is true for n = k.
3. Show that if the statement is true for n = k, then it must also be true for n = k + 1.

 

[hunt_mat]

It seems to me that the whole thing boils down to showing that for any n, there is an a>0? Is it this simple? The whole thing seems to be independent of m.

 

[Tedjn]

It does seem to be simple. The OP is correct in thinking that induction should be done on n. As Mark44 indicates, first prove the statement for n = 1. That is, fix m and find an a for which the inequality holds. Next, if n = k, and there exists an a for which the inequality holds, show that there is an a for which the inequality holds when n = k+1. Key is your choice of a; in this case, there are many easy choices.

 

[JonF]

I almost suspect the OP stated the problem wrong since it’s so easy to prove without induction:

n = n
n < n + a for a > 0
2^m(n) < 2^m(n + a) since 2^m > 0

so for free m,n and a>0; 2^m(n) < 2^m(n + a)