common-cases-of-proof-by-induction

Proof by induction – sequences

What are the steps for proof by induction with sequences?

• STEP 1: The basic step

  • Show the result is true for the base case

    • If the recursive relation formula for the next term involves the previous two terms then you need to show the position-to-term formula works the first two given terms which will be given as part of the definition of the sequence

  • This is normally n = 1 or 0 but it could be any integer

    • For example: To prove is the position-to-term formula for the recursive sequence : 

    • 

• STEP 2: The assumption step

  • Assume the result is true for n = k for some integer k

    • For example: Assume  is true

  • There is nothing to do for this step apart from writing down the assumption

• STEP 3: The inductive step

  • Using the assumption show the result is true for n = k + 1

  • It can be helpful to write down what you want to show

  • The assumption from STEP 2 will be needed at some point

    • For example: Want to show <img alt=”u subscript k plus 1 end subscript equals 3 to the power of k plus 1 end exponent minus 2″ data-mathml='<math ><semantics><mrow><msub><mi>u</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><msup><mn>3</mn><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msup><mo>-</mo><mn>2</mn></mrow><annotation encoding=”application/vnd.wiris.mtweb-params+json”>{“language”:”en”,”fontFamily”:”Times New Roman”,”fontSize”:”18″}</annotation></semantics></math>’ height=”29″ role=”math” src=”data:image/svg+xml;charset=utf8,%3Csvg%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F2000%2Fsvg%22%20xmlns%3Awrs%3D%22http%3A%2F%2Fwww.wiris.com%2Fxml%2Fmathml-extension%22%20height%3D%2229%22%20width%3D%22117%22%20wrs%3Abaseline%3D%2217%22%3E%3C!–MathML%3A%20%3Cmath%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F1998%2FMath%2FMathML%22%3E%3Cmsub%3E%3Cmi%3Eu%3C%2Fmi%3E%3Cmrow%3E%3Cmi%3Ek%3C%2Fmi%3E%3Cmo%3E%2B%3C%2Fmo%3E%3Cmn%3E1%3C%2Fmn%3E%3C%2Fmrow%3E%3C%2Fmsub%3E%3Cmo%3E%3D%3C%2Fmo%3E%3Cmsup%3E%3Cmn%3E3%3C%2Fmn%3E%3Cmrow%3E%3Cmi%3Ek%3C%2Fmi%3E%3Cmo%3E%2B%3C%2Fmo%3E%3Cmn%3E1%3C%2Fmn%3E%3C%2Fmrow%3E%3C%2Fmsup%3E%3Cmo%3E-%3C%2Fmo%3E%3Cmn%3E2%3C%2Fmn%3E%3C%2Fmath%3E–%3E%3Cdefs%3E%3Cstyle%20type%3D%22text%2Fcss%22%3E%40font-face%7Bfont-family%3A’math1819bfc9e6df1a8bf12affe7fd8’%3Bsrc%3Aurl(data%3Afont%2Ftruetype%3Bcharset%3Dutf-8%3Bbase64%2CAAEAAAAMAIAAAwBAT1MvMi7iBBMAAADMAAAATmNtYXDEvmKUAAABHAAAAERjdnQgDVUNBwAAAWAAAAA6Z2x5ZoPi2VsAAAGcAAABdWhlYWQQC2qxAAADFAAAADZoaGVhCGsXSAAAA0wAAAAkaG10eE2rRkcAAANwAAAAEGxvY2EAHTwYAAADgAAAABRtYXhwBT0FPgAAA5QAAAAgbmFtZaBxlY4AAAO0AAABn3Bvc3QB9wD6AAAFVAAAACBwcmVwa1uragAABXQAAAAUAAADSwGQAAUAAAQABAAAAAAABAAEAAAAAAAAAQEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACAgICAAAAAg1UADev96AAAD6ACWAAAAAAACAAEAAQAAABQAAwABAAAAFAAEADAAAAAIAAgAAgAAACsAPSIS%2F%2F8AAAArAD0iEv%2F%2F%2F9b%2Fxd3xAAEAAAAAAAAAAAAAAVQDLACAAQAAVgAqAlgCHgEOASwCLABaAYACgACgANQAgAAAAAAAAAArAFUAgACrANUBAAErAAcAAAACAFUAAAMAA6sAAwAHAAAzESERJSERIVUCq%2F2rAgD%2BAAOr%2FFVVAwAAAQCAAFUC1QKrAAsASQEYsgwBARQTELEAA%2FaxAQT1sAo8sQMF9bAIPLEFBPWwBjyxDQPmALEAABMQsQEG5LEBARMQsAU8sQME5bELBfWwBzyxCQTlMTATIREzESEVIREjESGAAQBVAQD%2FAFX%2FAAGrAQD%2FAFb%2FAAEAAAIAgADrAtUCFQADAAcAZRgBsAgQsAbUsAYQsAXUsAgQsAHUsAEQsADUsAYQsAc8sAUQsAQ8sAEQsAI8sAAQsAM8ALAIELAG1LAGELAH1LAHELAB1LABELAC1LAGELAFPLAHELAEPLABELAAPLACELADPDEwEyE1IR0BITWAAlX9qwJVAcBV1VVVAAEAgAFVAtUBqwADADAYAbAEELEAA%2FawAzyxAgf1sAE8sQUD5gCxAAATELEABuWxAAETELABPLEDBfWwAjwTIRUhgAJV%2FasBq1YAAAAAAQAAAAEAANV4zkFfDzz1AAMEAP%2F%2F%2F%2F%2FWOhNz%2F%2F%2F%2F%2F9Y6E3MAAP8gBIADqwAAAAoAAgABAAAAAAABAAAD6P9qAAAXcAAA%2F7YEgAABAAAAAAAAAAAAAAAAAAAABANSAFUDVgCAA1YAgANWAIAAAAAAAAAAKAAAAKEAAAErAAABdQABAAAABABeAAUAAAAAAAIAgAQAAAAAAAQAAN4AAAAAAAAAFQECAAAAAAAAAAEAEgAAAAAAAAAAAAIADgASAAAAAAAAAAMAMAAgAAAAAAAAAAQAEgBQAAAAAAAAAAUAFgBiAAAAAAAAAAYACQB4AAAAAAAAAAgAHACBAAEAAAAAAAEAEgAAAAEAAAAAAAIADgASAAEAAAAAAAMAMAAgAAEAAAAAAAQAEgBQAAEAAAAAAAUAFgBiAAEAAAAAAAYACQB4AAEAAAAAAAgAHACBAAMAAQQJAAEAEgAAAAMAAQQJAAIADgASAAMAAQQJAAMAMAAgAAMAAQQJAAQAEgBQAAMAAQQJAAUAFgBiAAMAAQQJAAYACQB4AAMAAQQJAAgAHACBAE0AYQB0AGgAIABGAG8AbgB0AFIAZQBnAHUAbABhAHIATQBhAHQAaABzACAARgBvAHIAIABNAG8AcgBlACAATQBhAHQAaAAgAEYAbwBuAHQATQBhAHQAaAAgAEYAbwBuAHQAVgBlAHIAcwBpAG8AbgAgADEALgAwTWF0aF9Gb250AE0AYQB0AGgAcwAgAEYAbwByACAATQBvAHIAZQAAAwAAAAAAAAH0APoAAAAAAAAAAAAAAAAAAAAAAAAAALkHEQAAjYUYALIAAAAVFBOxAAE%2F)format(‘truetype’)%3Bfont-weight%3Anormal%3Bfont-style%3Anormal%3B%7D%3C%2Fstyle%3E%3C%2Fdefs%3E%3Ctext%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2218%22%20font-style%3D%22italic%22%20text-anchor%3D%22middle%22%20x%3D%224.5%22%20y%3D%2217%22%3Eu%3C%2Ftext%3E%3Ctext%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2213%22%20font-style%3D%22italic%22%20text-anchor%3D%22middle%22%20x%3D%2213.5%22%20y%3D%2225%22%3Ek%3C%2Ftext%3E%3Ctext%20font-family%3D%22math1819bfc9e6df1a8bf12affe7fd8%22%20font-size%3D%2212%22%20text-anchor%3D%22middle%22%20x%3D%2224.5%22%20y%3D%2225%22%3E%2B%3C%2Ftext%3E%3Ctext%20font-family%3D%22Times%20New%20Roman%22%20font-size%3D%2213%22%20text-anchor%3D%22middle%22%20x%3D%2233.5%22%20y%3D%2225%22%3E1%3C%2Ftext%3E%3Ctext%20font-family%3