рдЬрд╛рджреВ рдирд┐рд░рдВрддрд░

рдЬрд╛рджреВ рдирд╛рдордХ рд╡рд░реНрдЧ рд╣реИрдВред рдареАрдХ рд╣реИ, рд╢рд╛рдпрдж рд╣рд░ рдХреЛрдИ рдЬрд╛рдирддрд╛ рд╣реИ рдХрд┐ рдРрд╕реЗ рд╡рд░реНрдЧреЛрдВ рдореЗрдВ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХрд╛ рдпреЛрдЧ рдХреНрд╖реИрддрд┐рдЬ, рд▓рдВрдмрд╡рдд рдФрд░ рдореБрдЦреНрдп рд╡рд┐рдХрд░реНрдг рд╕рдорд╛рди рд╣реИ, рдЕрд░реНрдерд╛рддреН, рд╕рдорд╛рди рд╕рдВрдЦреНрдпрд╛ рдХреЗ рдмрд░рд╛рдмрд░, рдЗрд╕ рд╕рдВрдЦреНрдпрд╛-рдпреЛрдЧ рдХреЛ рдЬрд╛рджреВ рд╕реНрдерд┐рд░рд╛рдВрдХ рдХрд╣рд╛ рдЬрд╛рддрд╛ рд╣реИ (рдЗрд╕рдХреЗ рдмрд╛рдж рдПрдо рдПрди , рдЬрд╣рд╛рдВ n рд╡рд░реНрдЧ рдХрд╛ рдЖрдХрд╛рд░ рд╣реИ; n> 2)ред рд╕реНрдХреВрд▓ рдореЗрдВ рд╡рд╛рдкрд╕, рдореБрдЭреЗ рдЗрд╕ рд╕реНрдерд┐рд░рд╛рдВрдХ рдХреА рдЧрдгрдирд╛ рдХрд░рдиреЗ рдХрд╛ рд╕реВрддреНрд░ рдпрд╛рдж рдЖрдпрд╛: M n = n * (n 2 + 1) / 2, рдпрд╣ рдореЗрд░реЗ рд▓рд┐рдП рд╕реНрдкрд╖реНрдЯ рдирд╣реАрдВ рдерд╛ рдХрд┐ рдпрд╣ рдХрд╣рд╛рдВ рд╕реЗ рдЖрдпрд╛ рд╣реИ ... рд╣рдо рдЗрд╕реЗ рдпрд╣рд╛рдВ рд╕реЗ рдирд┐рдХрд╛рд▓рдиреЗ рдХреА рдХреЛрд╢рд┐рд╢ рдХрд░реЗрдВрдЧреЗ, рд╣реЛ рд╕рдХрддрд╛ рд╣реИ рдХрд┐ рдХрд┐рд╕реА рдиреЗ рдкрд╣рд▓реЗ рд╣реА рдЗрд╕реЗ рдХрд╛рдЯ рд▓рд┐рдпрд╛ рд╣реЛ, рд╢рд╛рдпрдж рд╡рд╣реА рд╣реЛ , рд╢рд╛рдпрдж рдПрдХ рдЕрд▓рдЧ рддрд░реАрдХреЗ рд╕реЗ, рдпрд╣ рд╕рд┐рд░реНрдл рд▓рд┐рдЦрдиреЗ рд╕реЗ рдХреЛрдИ рдлрд░реНрдХ рдирд╣реАрдВ рдкрдбрд╝рддрд╛ред

рдПрдХ рдмрд╛рд░ рдлрд┐рд░ рд╕реЗ рд╡рд░реНрдЧреЛрдВ рдореЗрдВ рдкреНрд░рд╡реЗрд╢ рдХрд░рддреЗ рд╣реБрдП, рдПрдХ рдмрд╛рд░ рдореИрдВрдиреЗ рдРрд╕рд╛ рдХреБрдЫ рджреЗрдЦрд╛ред рдпрджрд┐ рдЖрдк рдмрд╛рдПрдВ рд╕реЗ рджрд╛рдПрдВ рдХреЙрд▓рдо рдореЗрдВ 1 рд╕реЗ n 2 рддрдХ рдХреА рд╕рдВрдЦреНрдпрд╛ рджрд░реНрдЬ рдХрд░рддреЗ рд╣реИрдВ, рддреЛ рдЖрдкрдХреЛ рдХрд┐рд╕реА рднреА рдореБрдЦреНрдп рд╡рд┐рдХрд░реНрдг рдкрд░ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдХреЛ рдЬреЛрдбрд╝рддреЗ рд╕рдордп рд╣рдореЗрд╢рд╛ рдЬрд╛рджреВ рдХреА рд╕реНрдерд┐рддрд┐ рдорд┐рд▓рддреА рд╣реИ, рдпрд╣рд╛рдВ рдЖрдк рджреЗрдЦ рд╕рдХрддреЗ рд╣реИрдВ:

рдПрдо 3 :
рез рек 7
реи рел 8
рей рем реп

рдПрдо 4 :
рез рел реп резрей
реи рем резреж резрек
3 7 11 15
рек 4 резреи резрем

рд╕реВрддреНрд░ рдХреЗ рдЕрдиреБрд╕рд╛рд░:

рдПрдо 3 = рдПрди * (рдПрди 2 + 1) / 2 = 3 * (3 * 3 + 1) / 2 = 30/2 = 15
рдПрдо 4 = рдПрди * (рдПрди 2 + 1) / 2 = 4 * (4 * 4 + 1) / 2 = 68/2 = 34

рддрд┐рд░рдЫреЗ (рдКрдкрд░ рдмреЛрд▓реНрдб рдореЗрдВ рджрд┐рдЦрд╛рдпрд╛ рдЧрдпрд╛ рд╣реИ):

рдПрдо 3 = 1 + 5 + 9 = 15
рдПрдо 4 = 1 + 6 + 11 + 16 = 34

рд╕реВрддреНрд░ рдХреЗ рд╡рд┐рдкрд░реАрдд, рд╡рд┐рдХрд░реНрдг рдПрдХ рдЙрддреНрддрд░ рджреЗрдиреЗ рдореЗрдВ рд╕рдХреНрд╖рдо рд╣реИрдВ рдХрд┐ рдХреНрдпрд╛ рд╣реЛ рд░рд╣рд╛ рд╣реИред рд╡рд┐рдХрд░реНрдгреЛрдВ рдкрд░ рд╕рдВрдЦреНрдпрд╛рдУрдВ рдкрд░ рд╡рд┐рдЪрд╛рд░ рдХрд░реЗрдВ:

рдПрдо 3 = 1 + 5 + 9
рдПрдо рек = рез + рем + резрез + резрем

рд╣рдо рдЗрд╕реЗ рдЕрд▓рдЧ рддрд░рд╣ рд╕реЗ рд▓рд┐рдЦрддреЗ рд╣реИрдВ:

M 3 = 1 + (3 + 2) + (3 * 2 + 3)
M 4 = 1 + (4 + 2) + (4 * 2 + 3) + (4 * 3 + 4)

рдХреНрдпрд╛ рдЖрдкрдиреЗ рдЧреМрд░ рдХрд┐рдпрд╛ рд╣реИ? рдЕрдм n рд╕реЗ рд╕рд╛рдорд╛рдиреНрдп рд░реВрдк рдореЗрдВ:

M n = 1 + (n + 2) + (n * 2 + 3) + (n * 3 + 4) + (n * 4 + 5) + ... + (n * (n-1) + n)

рдЗрд╕реЗ рдлрд┐рд░ рд╕реЗ рд╕рдВрдЧрдард┐рдд рдХрд░реЗрдВ (рдмреЛрд▓реНрдб)
M n = 1 + (n + 2 ) + (n * 2 + 3 ) + (n * 3 + 4 ) + (n * 4 + 5 ) + ... + (n * (n-1) + n )

рдФрд░ рдпрд╣ (рдмреЛрд▓реНрдб рдореЗрдВ рд╣рд╛рдЗрд▓рд╛рдЗрдЯ рдХрд┐рдпрд╛ рдЧрдпрд╛)
M n = 1 + ( n + 2) + ( n * 2 + 3) + ( n * 3 + 4) + ( n * 4 + 5) + ... + ( n * (n-1) + n)

рдФрд░:

M n = (1 + 2 + 3 + 4 + 5 + ... + n) + (n + n * 2 + n * 3 + n * 4 + ... + n * (n-1))

рдПрди рдмреНрд░реИрдХреЗрдЯ рд╕реЗ рдмрд╛рд╣рд░ рд░рдЦреЗрдВ:

M n = (1 + 2 + 3 + 4 + 5 + ... + n) + n * (1 + 2 + 3 + 4 + ... + (n-1)) [1]

рдЕрдм рд╣рдо рдПрдХ рдирдпрд╛ рдЕрдВрдХрди рдкреНрд░рд╕реНрддреБрдд рдХрд░рддреЗ рд╣реИрдВ,

S n = 1 + 2 + 3 + ... + n [2]
рддреЛ
S n-1 = 1 + 2 + 3 + ... + (n-1) = S n - n [3]

рдЕрдм рд╣рдо рд╕реВрддреНрд░ [1] рдХреЛ рдзреНрдпрд╛рди рдореЗрдВ рд░рдЦрддреЗ рд╣реБрдП [2] рдФрд░ [рей] рдХреЛ рдлрд┐рд░ рд╕реЗ рд▓рд┐рдЦрддреЗ рд╣реИрдВ, рдФрд░ рдкреНрд░рд╛рдкреНрдд рдХрд░рддреЗ рд╣реИрдВ:

M n = S n + n * (S n - n) [4]

рдпрд╛ рддреЛ:

рдПрдо рдПрди = рдПрд╕ рдПрди * (рдПрди + 1) - рдПрди 2

[5]

рдЗрд╕реЗ рдзреНрдпрд╛рди рдореЗрдВ рд░рдЦрддреЗ рд╣реБрдП S n -



рд╕реНрдкрд╖реНрдЯ рд░реВрдк рд╕реЗ рд╕реВрддреНрд░ S n = n 2/2 + n / 2 = n * (n + 1) / 2, рджреНрд╡рд╛рд░рд╛ рдкрд░рд┐рдХрд▓рд┐рдд
[5] рдореЗрдВ рд╕реНрдерд╛рдирд╛рдкрдиреНрди рдХрд░реЗрдВ:

M n = S n * (n + 1) - n 2 = n * (n + 1) * (n + 1) / 2 - n 2 = n * (n 2 + 2 * n + 1 - 2 * n) / 2 = рдПрди * (рдПрди 2 + 1) / 2

рдПрдо рдПрди = рдПрди * (рдПрди 2 + 1) / 2

QED

Source: https://habr.com/ru/post/hi418725/


All Articles