Proof using Induction

[Ryuna]

Can someone help me solve the following problems from Discrete Maths, using induction to prove them

Thanks in advance

 

[mmm4444bot]

Hi Ryuna:

The system delayed your post, probably due to the outside link. If you upload your images to our server, instead, your posts will appear without delay. Otherwise, you may wait until a moderator approves such posts.

We prefer one exercise per thread.

Are you already familiar with the basic steps of an induction proof? If so, what have you done (or thought about) with these exercises so far? At what step are you stuck?

Also, please read the forum guidelines; here's a link to the summary page. Links to the complete guidelines and rules appear near the bottom of the summary page.

Thank you :cool:

 

[stapel]

Can someone help me solve the following problems from Discrete Maths, using induction to prove them

You've shown no work for any of these, not even the base "show it's true for n = 1" step, so I'm guessing you'd like some lesson instruction first? If so, there's a listing of lessons available here.

Once you've studied at least two lessons from the link, please attempt the exercises.

\(\displaystyle \mbox{a) }\, \sum_{k=1}^n\, 32^{k-1}\, =\, 3(2^n\, -\, 1)\)

The base step requires that you plug "1" in for "n" on either side of the equation. Verify that the resulting values are the same. So:

. . . . .\(\displaystyle \sum_{k=1}^1\, 32^{k-1}\, =\, 32^{1-1}\, =\, 32^0\, =\, 1\)

. . . . .\(\displaystyle 3(2^1\, -\, 1)\, =\, 3(2\, -\, 1)\, =\, 3(1)\, =\, 3\)

So clearly this one isn't true, and you're done.

\(\displaystyle \mbox{b) }\,5\, |\, (6^n\, -\, 1)\, \mbox{ for }\, n\, \geq\, 1\)

I will guess that the "pipe" character after the "5" is meant to say "divides". So start with the "n=1" case. If that's true, then clearly write out the "assumption" step at the generic unspecified number "n=k"; namely:

. . . . .\(\displaystyle \mbox{For }\, n\, =\, k,\, \mbox{ assume that }\, 5\, |\, (6^k\, -\, 1)\)

Then proceed to the inductive part with "n=k+1".

\(\displaystyle \mbox{c) }\, 1\, +\, \frac{1}{2}\, +\, \frac{1}{3}\, +\, ...\, +\, \frac{1}{n}\, >\, \frac{2n}{n\, +\, 1}\, \mbox{ for }\, n\, \geq\, 2.\)

After you've done the base and assumption step, proceed to the inductive part. The initial set-up will probably be something like:

. . . . .\(\displaystyle 1\, +\, \frac{1}{2}\, +\, \frac{1}{3}\, +\, ...\, +\, \frac{1}{k}\,+\, \frac{1}{k\, +\, 1}\, >\, \frac{2k}{k\, +\, 1}\, +\, \frac{1}{k\, +\, 1}\)

The first fraction on the right-hand side of the equation, obviously, displaying where the "assumption" info has been plugged in. Then go from there, and see where it leads.

If you get stuck, please reply showing all of your steps so far. Thank you! :wink: