Urgent! Inductions Question (1 Viewer)

kevda1st · Nov 27, 2008

I have a test tomorrow and cant solve this...:

prove If n is even then <meta http-equiv="Content-Type" content="text/html; charset=utf-8"><meta name="ProgId" content="Word.Document"><meta name="Generator" content="Microsoft Word 12"><meta name="Originator" content="Microsoft Word 12"><link rel="File-List" href="file:///C:%5CDOCUME%7E1%5CKevin%5CLOCALS%7E1%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_filelist.xml"><link rel="themeData" href="file:///C:%5CDOCUME%7E1%5CKevin%5CLOCALS%7E1%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_themedata.thmx"><link rel="colorSchemeMapping" href="file:///C:%5CDOCUME%7E1%5CKevin%5CLOCALS%7E1%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_colorschememapping.xml"><!--[if gte mso 9]><xml> <w:WordDocument> <w:View>Normal</w:View> <w:Zoom>0</w:Zoom> <w:TrackMoves/> <w:TrackFormatting/> <w

unctuationKerning/> <w:ValidateAgainstSchemas/> <w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid> <w:IgnoreMixedContent>false</w:IgnoreMixedContent> <w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText> <w

oNotPromoteQF/> <w:LidThemeOther>EN-AU</w:LidThemeOther> <w:LidThemeAsian>KO</w:LidThemeAsian> <w:LidThemeComplexScript>X-NONE</w:LidThemeComplexScript> <w:Compatibility> <w:BreakWrappedTables/> <w:SnapToGridInCell/> <w:WrapTextWithPunct/> <w:UseAsianBreakRules/> <w

ontGrowAutofit/> <w:SplitPgBreakAndParaMark/> <w

ontVertAlignCellWithSp/> <w

ontBreakConstrainedForcedTables/> <w

ontVertAlignInTxbx/> <w:Word11KerningPairs/> <w:CachedColBalance/> <w:UseFELayout/> </w:Compatibility> <w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel> <m:mathPr> <m:mathFont m:val="Cambria Math"/> <m:brkBin m:val="before"/> <m:brkBinSub m:val="--"/> <m:smallFrac m:val="off"/> <m:dispDef/> <m:lMargin m:val="0"/> <m:rMargin m:val="0"/> <m:defJc m:val="centerGroup"/> <m:wrapIndent m:val="1440"/> <m:intLim m:val="subSup"/> <m:naryLim m:val="undOvr"/> </m:mathPr></w:WordDocument> </xml><![endif]--><style> <!-- /* Font Definitions */ @font-face {font-family:바탕; panose-1:2 3 6 0 0 1 1 1 1 1; mso-font-alt:Batang; mso-font-charset:129; mso-generic-font-family:roman; mso-font-pitch:variable; mso-font-signature:-1342176593 1775729915 48 0 524447 0;} @font-face {font-family:"Cambria Math"; panose-1:2 4 5 3 5 4 6 3 2 4; mso-font-charset:0; mso-generic-font-family:roman; mso-font-pitch:variable; mso-font-signature:-1610611985 1107304683 0 0 159 0;} @font-face {font-family:"맑은 *딕"; panose-1:0 0 0 0 0 0 0 0 0 0; mso-font-charset:129; mso-generic-font-family:roman; mso-font-format

ther; mso-font-pitch:auto; mso-font-signature:0 0 0 0 0 0;} @font-face {font-family:Calibri; panose-1:2 15 5 2 2 2 4 3 2 4; mso-font-charset:0; mso-generic-font-family:swiss; mso-font-pitch:variable; mso-font-signature:-1610611985 1073750139 0 0 159 0;} @font-face {font-family:"\@맑은 *딕"; panose-1:0 0 0 0 0 0 0 0 0 0; mso-font-charset:129; mso-generic-font-family:roman; mso-font-format

ther; mso-font-pitch:auto; mso-font-signature:0 0 0 0 0 0;} @font-face {font-family:"\@바탕"; panose-1:2 3 6 0 0 1 1 1 1 1; mso-font-charset:129; mso-generic-font-family:roman; mso-font-pitch:variable; mso-font-signature:-1342176593 1775729915 48 0 524447 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-unhide:no; mso-style-qformat:yes; mso-style-parent:""; margin-top:0cm; margin-right:0cm; margin-bottom:10.0pt; margin-left:0cm; line-height:115%; mso-pagination:widow-orphan; font-size:11.0pt; font-family:"Calibri","sans-serif"; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:"맑은 *딕"; mso-fareast-theme-font:minor-fareast; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} .MsoChpDefault {mso-style-type:export-only; mso-default-props:yes; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:"맑은 *딕"; mso-fareast-theme-font:minor-fareast; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} .MsoPapDefault {mso-style-type:export-only; margin-bottom:10.0pt; line-height:115%;} @page Section1 {size:595.3pt 841.9pt; margin:3.0cm 72.0pt 72.0pt 72.0pt; mso-header-margin:35.4pt; mso-footer-margin:35.4pt; mso-paper-source:0;} div.Section1 {page:Section1;} --> </style> n^2 + 2n is divisible by 8

Trebla · Nov 27, 2008

For n = 2
2² + 2(2) = 8 x 1
Thus statement is true for n = 2
Assume the statement is true for n = 2k (use 2k to ensure n is even)
4k² + 4k = 8M (for some integer M)
Required to prove the statement is true for n = 2k + 2 (the next even number)
(2k + 2)² + 2(2k + 2) = 8N (for some integer N)
LHS = (2k + 2)² + 2(2k + 2)
= 4k² + 8k + 4 + 4k + 4
= 4k² + 4k + 8k + 8
= 8M + 8k + 8 by assumption
= 8(M + k + 1)
= 8N (where N = M + k + 1 which is an integer)
= RHS
If the statement is true for n = 2k, it is also true for n = 2k + 2.
Since the statement is true for n = 2, it is true for all other even numbers n.

jcurry · Nov 27, 2008

kevda1st said:
I have a test tomorrow and cant solve this...:

prove If n is even then <META content=Word.Document name=ProgId><META content="Microsoft Word 12" name=Generator><META content="Microsoft Word 12" name=Originator><LINK href="file:///C:%5CDOCUME%7E1%5CKevin%5CLOCALS%7E1%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_filelist.xml" rel=File-List><STYLE> v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} </STYLE><LINK href="file:///C:%5CDOCUME%7E1%5CKevin%5CLOCALS%7E1%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_themedata.thmx" rel=themeData><LINK href="file:///C:%5CDOCUME%7E1%5CKevin%5CLOCALS%7E1%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_colorschememapping.xml" rel=colorSchemeMapping><STYLE>  </STYLE>n^2 + 2n is divisible by 8

someone beat me to it

3.14159potato26 · Nov 27, 2008

kevda1st said:
prove If n is even then  n^2 + 2n is divisible by 8

Since the question doesn't explicitly say that you have to use induction to solve it (although induction is much simpler), you can also use an analytical method to prove this result.
[Syntax: a | b means b is divisible by a]
Now, from the question, 2 | n, and we need to prove that 8 | n^2 + 2n
Therefore, let n = 2k, where k is some integer.
It follows that:
n^2 + 2n
= (2k)^2 + 2 * (2k)
= 4k^2 + 4k
= 4k(k+1)
It is trivial that k is either odd or even.
If k is odd, let k = 2m + 1, where m is some integer.
4k(k+1)
=4(2m+1)((2m+1)+1)
=4(2m+1)(2m+2)
=4(2m+1)*2(m+1)
=8(2m+1)(m+1), which is divisible by 8.
Therefore, 8 | n^2 + 2n applies when k is odd.
If k is even, let k = 2m, where m is some integer.
4k(k+1)
=4(2m)(2m+1)
=8m(2m+1), which is divisible by 8.
Therefore, 8 | n^2 + 2n applies also when k is even.
Since 8 | n^2 + 2n applies both when k is odd or even, therefore it applies for all k.
Since it applies for all k, 8 | n^2 + 2n is true for all n, and thus is proven.
Q.E.D.
The analytical method relies on dissecting the problem into smaller parts that can be proven easily. Since all parts can be proven, therefore the result is proven. Again, I emphasize that it is more difficult and longer than induction, but it helps in some cases in which induction is difficult or cannot be applied.

Urgent! Inductions Question (1 Viewer)

kevda1st

Member

Trebla

Administrator

jcurry

Member

3.14159potato26

New Member

Users Who Are Viewing This Thread (Users: 0, Guests: 1)