### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 1Inductive.pdf CSS342

UW

GPA 3.5

### View Full Document

## 216

## 2

1 review

## Popular in Data Structure & Algorithm Analysys

## Popular in Computer Science and Engineering

This 3 page Study Guide was uploaded by NGHIEP NGO on Wednesday November 5, 2014. The Study Guide belongs to CSS342 at University of Washington taught by Dr. Carol Zander in Fall. Since its upload, it has received 216 views. For similar materials see Data Structure & Algorithm Analysys in Computer Science and Engineering at University of Washington.

## Reviews for 1Inductive.pdf

Better than the professor's notes. I could actually understand what the heck was going on. Will be back for help in this class.

-*Ewell Bashirian*

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 11/05/14

1 Inductive Friday June 6 2014 1206 AM 1quot39itiiEiii h1iEIii1 tiii3h I l39I iiiiquot393ii iIEIIquoti in general nHt lien iatiis indimtinn eriii the d tii that assert that Pin is 39lFllE39 fist sli pesitiiiie Integers H where Pifri is a priIJnsirt i fiiinitintL A 1 h3r nistheiTiatiia liitIue nvii has time a sup where we shew ist Fquot1 is h39iie i EIl39Iiii1IiiIllE quot E P iliriiere we that all integers i if J gt ir1u ls true then Phi its is PiiiN39CiFtLE I iquot ri 1THEMsiTi C 1L ii 39iquotjZiiL39I iZquoti i39 Equoti f iquot Tn Pm is true hzir slili iIlquotiu39 E ii where Pita is s itiiznisili flillEIIhilZL we ennsplete steps BASIS STEP that iFquotl is i139iie IND ii39IEquotquotii 39E 5TEF shmir that the H 1 all integers L itiniiai stateiiient P39it r Pitt 3391 is I l39lilE iilquot E3335iisIP LE 1 B that iii2 is a P integer then l I 1 l3HIii E iei nisH39 Let Pin iie theneeiesitiien Hist the sumnf 39IE I395l39ii itiiireintegers 1 E e r E quot3939 quot 3 s i i n1ia must en tum nimgs tn 0 thatbFifi39Zia is ime H 1 Ei U 1 iquotIIa39EIlTiE39quotF s1FE TIIii1quotiE1lJ39ili39I1If 1iJiPihlIIS FllE39 lTIIEi39i1i i IEiiIiiillIIfiIIU5ITEIIEIEIIEHI PE ihmJiE5 Fifi 1 iE Ii IEi39T39iifitlEn3 H 1t1ii E39i5 i395 STEP Fifi is hue O 1 M Ike ieflhaiiti side iii this Etijlila til is 1 IEEEIISEA i is the sum the iTll39SiI1iI ii39EIlfEjgEi1T1E iigIit iaiiIi side is int i Emit iII39IJ iquot I lI393il i l13r sii hstitiiithig 1 iitJDUCTI TEE STEP Fliii the iniiiisrstiiire hjtp l i we s iinie that Fit heiiis fni mi sr hirwisjr integer ii That is we EI5SliiI39I IE that E5iEff 3 ting sigehrsi iiti istEiisisIhn ica sense O ing Liniier this EI5SliI39I IIi it must he ii that P ii 1 is fII IET nanielly iat ii iii39 i I 1 iii 1iiic E 2 E 1smiIIft1 i is slim hues l39E mid it 1 m htith sides Ii39IEquot III39IEiquotlZ il IZliZ1lil39I Fquoti we lx 13v WUquotE k gn HhIlEl1l E tk1iitk2i iiI iiii This last eiiiiistitin that Phi i is WIIE iiiititer the msn that iP iirji is 11 39E This enmpietes the LI39ldl39ID quotil39E step v have qpleteti the i 2 is t an the iillilllI1l739 I1Iquoti39E steps sin by irnathei39naiiiai iiiti iiitl r knew that Fiji jils quotZi39lIi15J 391iElIIllEjgEI7 t 39I1fhIHi I 39ili39E39h quotiI3939EA2Ii iIii I3939EIil that E H ir sin JlI39E Is all pnsitisre integers in fm nrathematieai indnetiin is a ti iinifling III39IEt1l39E39lT t all irtise inteeers Ratlien It is a iirnanf nie f tl nrnirine such resiii enize are ennieirture In CSS 342 CquotMquotM Page 1 Hl I 1 I JfE 0AK i39III 39FLl1EIIJ i39li39 IlIl39Eg EIEI3 FL quot1 are muted ITI HIII ElTI I IIIHE39EI indmt nn is nut 3 lm Fm n irng III39IEll39E39lTI S 8 integers H IITEl39 II is 3 prmaf li39I Equot fur prmring such resul wannaE J are mnjeciuraazfl In Tnanr all pusirtirwel Enmmple E I lng n thematlwzal lJ1duItlusn In XF summatlrnn furmmlla will FI1rmuIla lE and liE39l 3 nnj Iu CSS 342 CquotMquotM Page 2 Exa m p I es Tuesday June 1 Z 14 719 PM 1 Prove the sum of the rst n odd number is n2 Prove 239112i 1 n2 follow the following steps 39 Base case show true when n1 39 Whenn 1LHS 1RHS 1 39 Induction Hypothesis assume the above expression is true from 1 up to k means that k Z2i 1 k2 i1 39 Induction Steps show that it is true at k1 or Pk1 true means k1 Z2i 1 k 12 i 1 Wehave k1 k z2z 1 Z2i 12k1 1 k22k1 k12 l1 l1 Therefore Pk1 is true a 239112i 1 112 true 2 Prove n gt n2 for all n 2 4 Proof by induction on n Base case show true when n 4 41gtlt2gtlt3gtlt424 4216 therefore 4 gt 42 39 Induction hypothesis assume the expression is true up through k that is k gt k2 39 Induction step show that it is true at k1 k1kxk1 k 12 k 1k 1 We want to go one more step to prove k gt k 1 then we reach to conclusion 3 Show that postage of gt 4 cents can be archived using only 2 cent and 5 cent stamps Proof by induction on number of cents 39 Base case show that 4 cents can be archive using only 2 cent stamp and 5 cent stamp We can use 2 x 2 cents stamps to make 4 cents I Induction hypothesis assume this is true up through k that is k cents can be make using 2 amp 5 cents stamps 39 Induction step show that k1 cent can be archive using only 2 amp 5 cents stamp Proof this is a constructive proof By inductive proof k cents can made use 2 and 5 cents stamp Therefore either 2 or 5 cents or both are used Case 1 All 2 cent are used Case 2 At least one 5 cent are used Case 3 Both are used 4 Prove the graph with n nodes and an edge from each node to every other node no edge to itself has a total of nn1 2 edges Proof by induction on n number of nodes 39 Base case no glue of base case show it true at zero smallest number that make expression true If there is no node there is no edge With n O nn 12 0 It is true Inductive Hypothesis Assume it is true up to k means if there is k node then the edge is kk 12 We need to prove it true at k1 means If we have k1 nodes we must have k1k1 12 k1k 2 edges Inductive steps Notice that when I add one node to the graph of k nodes the number edge increase k to connect all other nodes to the new node So total edge edgek 1 edgek k kk 1 k k2 k 2k kk 1 Therefore is true So with n nodes the graph will have nn 12 edges CSS 342 CquotMquotM Page 1 lEiquotJETlquot JT Intquot il39iIiut139r Tquot1rtar L luiI1I I JEM1EJlIIquotld ilIlampl39 y39 L1quotuu t tH1 15 lI39quotL39IEII Ieuua ta 1u39t llj539 2 I uI If1quot39 l1 i39ltnuI1quot llquotI139tn1 39 lay ii1rInlI1Ir39l nn I HM 39rlI1I InlHr39 Miltquot rwl llillnt 1lltii quotI 15 1t39f 1quottn39 5 I iiiI39nti1t 1 39II fI39J1I39li E39lE li39I39It39r139 39trm 1t39i1H nlu l1quot7VlI Il quotlJIilitilhi ml at uiiI39 n1 u1nlI39 i 39ifII 11 1I39139lI 1 1 J I EI il Ilquot l39139i1tnquotft39 IllquotEquot iquot uh39iquott l1 Iquot lit quotsI li5 TH11139 23939 I uuu 1ti l I39 r EWL l I39El 11lll d quotZrll Lu m39rru IiIu 1 mitnp1ttu ltijI nL 39II f39s lI n1t quottiquot ilill Ali I l il Equotua t39quotIli llmi Eli I H l iinm tta PvW 391HII 39I5li H1fI1tn139 tI1 tt wjttllt L Li I IIiquotquot3939 IE39llH quotquotvllETl339Tlh llt39w39 utftt UlJIZ rJ391lIi i l1 v vquott1 ti t t 4 u39i39ll3911 ls ll i39E392li Tll1lf39fl lIJiI l li 39 lltu i EIt39lLElEquotIiiJi i u391tmair lllu Mblliltl li JILi1 lIHi39 uili n1t1 1ltrr ia P i 39iIl139Hll i39quotr ee uquotrquott51 la O Time uu f71 if Rq Et39139el5 Fe1re39I5

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.